Find the minimum window in s which contains all characters of t.
This problem follows the Variable Window + Map pattern, commonly found in the Sliding Window category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Expand right to include all chars. Shrink left to minimize. Track with frequency maps.
Track 'formed' (characters meeting their required count) separately from individual counts — this avoids re-scanning the frequency map each iteration.
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
result = ""
for right in range(len(s)):
have[s[right]] = have.get(s[right], 0) + 1
if s[right] in need and have[s[right]] == need[s[right]]:
formed += 1
while formed == required:
window = s[left:right+1]
if not result or len(window) < len(result):
result = window
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return resultPractice Minimum Window Substring and similar Sliding Window problems with flashcards. Build pattern recognition through active recall.
Practice this problem