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 (LeetCode 76) ───

# Pattern: Sliding window + need/have maps

# Time: O(n+m) Space: O(m)

# 1. need = Counter(t), have = {}, have_count = 0, required = len(need)

# 2. Expand: 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

# 3. 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

# 4. Return: s[best_start:best_start+best_len]

# Vars: need, have, have_count, required

▼ your implementation ▼

Verify your solution: