AI Hints
Home›DSA in Python Tutorial›More Practice: Sets, Windows and Trees
DSA in Python · Lesson 125 of 132

Practice: Minimum Window Substring

A shrinking window.

⏱ 2 min read▶ Video at 2:28:50🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Minimum Window Substring
From the video: Practice: Minimum Window Substring
  • 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.

min_window.pypython
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"))
Output
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.

keyvalue
Growmove right
Shrinkmove left while valid
Recordthe best window
CostO(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)
Next up: Practice: Serialize a Tree — tree to string and back