Practice: Minimum Window Substring
A shrinking window.
Find the shortest part of a string that contains every letter of another string. In ADOBECODEBANC, the shortest part containing A, B, and C is BANC. This is one of the hardest sliding window problems.

- Shortest part with all the letters
- ADOBECODEBANC
- Answer: BANC
Grow, then shrink
Need counts the letters still missing. The right edge grows the window until nothing is missing. Then the left edge shrinks it as far as it can, while it still has everything, and we record the best window. Run it. BANC, four letters long.
from collections import Counter
def min_window(s, t):
need, missing = Counter(t), len(t)
best, left = "", 0
for right, ch in enumerate(s, 1):
missing -= need[ch] > 0
need[ch] -= 1
if missing == 0:
while need[s[left]] < 0:
need[s[left]] += 1; left += 1
if not best or right - left < len(best):
best = s[left:right]
return best
print(min_window("ADOBECODEBANC", "ABC"))BANC
The window pattern
Every sliding window problem has the same shape. Grow the right edge to include more. Shrink the left edge while the window is still valid. And record the best answer as you go. Each character enters and leaves the window once, so it's O of N.
| key | value |
|---|---|
| Grow | move right |
| Shrink | move left while valid |
| Record | the best window |
| Cost | O(n) |
Summary
Grow the window until it's valid, then shrink it from the left, recording the best. Next, turning a tree into a string, and back.
Key takeaways- Counter of needs
- Grow, then shrink
- O(n)