The tell: Shortest window containing every character of a target, counts included.
How you get there
1Track how many distinct required characters are currently satisfied.
2Expand right until the window is valid, then contract left while it stays valid.
3Record the best window each time it is valid, before contracting further.
Solution
Python
from collections import Counter
def min_window(s: str, t: str) -> str:
if not t or not s:
return ""
need = Counter(t)
missing = len(need) # distinct characters still unsatisfied
window: Counter = Counter()
best = (float("inf"), 0, 0)
start = 0
for i, ch in enumerate(s):
window[ch] += 1
if ch in need and window[ch] == need[ch]:
missing -= 1
while missing == 0:
if i - start + 1 < best[0]:
best = (i - start + 1, start, i)
left = s[start]
window[left] -= 1
if left in need and window[left] < need[left]:
missing += 1
start += 1
return "" if best[0] == float("inf") else s[best[1] : best[2] + 1]
Time
O(n + m)
Space
O(m)
What goes wrong
Comparing whole Counters on each step is correct but O(alphabet) per character; the satisfied counter avoids it.