Minimum Window Substring

Signal

"Shortest substring that contains all of X" is the mirror image of the longest-under-a-constraint shape: expand right until the window is valid, then shrink left as far as it stays valid — a variable window driven by a coverage condition, not a length budget.

Approach

Track how many of each required character are still needed. Expand the right edge, decrementing the needed count for each character consumed and counting how many distinct required characters have been fully satisfied. Once every required character is satisfied, the window is valid — shrink from the left as far as possible while it stays valid, recording the smallest valid window seen, then keep expanding right.

Skeleton

need = count(t)
missing = distinct chars in need
left = 0
best = (infinity, none)
for right, c in enumerate(s):
    if c in need:
        need[c] -= 1
        if need[c] == 0: missing -= 1
    while missing == 0:
        record window if smaller than best
        if s[left] in need:
            need[s[left]] += 1
            if need[s[left]] > 0: missing += 1
        left += 1

Solution

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)
    left = 0
    best_len = float("inf")
    best_start = 0

    for right, c in enumerate(s):
        if c in need:
            need[c] -= 1
            if need[c] == 0:
                missing -= 1
        while missing == 0:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left
            left_char = s[left]
            if left_char in need:
                need[left_char] += 1
                if need[left_char] > 0:
                    missing += 1
            left += 1

    return "" if best_len == float("inf") else s[best_start : best_start + best_len]

Complexity

O(|s| + |t|) time — right and left each advance across s at most once; building need costs O(|t|). O(|t|) space for the count map.

Pitfalls

• Using an emptied dict (len(need) == 0) to mean "satisfied" instead of a missing counter breaks when a character's count dips to 0 and back above it — track distinct fully-satisfied characters, not dict emptiness.
• Re-incrementing need[char] above 0 during a shrink must also re-increment missing — easy to forget, which then reports a window as valid when it no longer covers t.
• Characters in s that never appear in t should never touch need or missing at all — they only affect window length, not validity.