Minimum Window Substring

LeetCode 76 • Hard • Sliding Window

Find the minimum window in s that contains all characters from t.
Input: s = "ADOBECODEBANC", t = "ABC" → Output: "BANC"

TimeO(n+m)s + t

SpaceO(m)need + have maps

Window: — Have: — Best: —

Window

Right (expand)

Shrink

Target chars

Window

—

Have

—

Best

—

Speed:

Ready

Press Play. Expand right until window has all chars from t. Then shrink from left while valid. Track minimum window.

⌨ Type It

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ MINIMUM WINDOW SUBSTRING — SLIDING WINDOW ═══

PATTERN ▸ need/have maps + have_count O(n+m) · O(m)

① INIT

need = Counter(t)

have = {}, have_count = 0, required = len(need)

② EXPAND RIGHT

for right in range(len(s)):

have[s[right]] += 1

if s[right] in need and have[s[right]] == need[s[right]]: have_count += 1

③ SHRINK WHILE VALID

while have_count == required:

update best; have[s[left]] -= 1; if have[s[left]] < need[s[left]]: have_count -= 1; left += 1

④ RETURN

return s[best_start:best_start+best_len]

▼ your implementation ▼

Verify your solution: