Minimum Window Substring (LeetCode 76)

The problem

You get two strings s and t. Return the shortest substring of s that contains every character of t, including duplicates (if t has two As, the window needs at least two). If no such substring exists, return "".

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

"BANC" contains an A, a B and a C, and no shorter piece of s does.

How to think about it

Start with brute force. Check every substring of s, test whether it covers t’s counts, and keep the shortest. That’s O(n²) substrings, each with a coverage check: O(n²) at best, O(n³) if done naively.

Notice the monotonic shape. If a window covers t, every bigger window that contains it also covers t. If a window doesn’t cover t, every window inside it doesn’t either. That’s exactly when the grow-then-shrink sliding window works.

The key insight: two counters make coverage an O(1) check. Keep need[c]: how many more of c the window still needs (it goes negative when the window has spares). Keep missing: the total number of characters of t still not covered. When a new character arrives and need[c] > 0, it was genuinely needed, so missing drops by one. Either way, need[c] drops by one. When missing hits 0, the window covers t.

Then shrink to the smallest valid window. From the left, any character with need[c] < 0 is a spare (or not in t at all), so you can drop it without breaking coverage. Stop at the first character the window actually needs. Compare that window with the best so far. Every character enters once and leaves once, so it’s O(n).

Which pattern is this? A variable-size sliding window, “minimum length” flavour, with a frequency map. The tell is “smallest substring that contains all of …”.

Approach

1. Return "" if either string is empty. Set need = Counter(t), missing = len(t), lo = 0, and start = end = 0 for the best window.
2. For each right edge r (1-indexed, so the window is s[lo:r]) with character c: if need[c] > 0, decrease missing. Then decrease need[c].
3. If missing == 0, move lo right while need[s[lo]] < 0, adding each dropped character back into need.
4. If this window is the first valid one or shorter than the best, save start, end = lo, r.
5. Return s[start:end], which is "" if no window was ever valid.

Solution

from collections import Counter

def min_window(s, t):
    if not t or not s: return ""
    need = Counter(t); missing = len(t); start = end = 0; lo = 0
    for r, c in enumerate(s, 1):                  # window is s[lo:r]
        if need[c] > 0: missing -= 1              # a character we still needed
        need[c] -= 1
        if missing == 0:                          # window covers t
            while need[s[lo]] < 0:                # drop spares from the left
                need[s[lo]] += 1; lo += 1
            if end == 0 or r - lo < end - start: start, end = lo, r
    return s[start:end]
# min_window("ADOBECODEBANC", "ABC") -> "BANC"

Dry run

On s = "ADOBECODEBANC", t = "ABC" (only the steps that change something important):

The answer is “BANC”.

Complexity

• Time: O(|s| + |t|). Building need is O(|t|); then r and lo each move through s once.
• Space: O(charset). The need map holds the characters of t plus any others seen in s.

Edge cases and pitfalls

• No valid window (s = "a", t = "b"): end stays 0 and s[0:0] is "".
• Duplicates in t (t = "AA") are handled by counts. A set-based check would accept a single A.
• t longer than s can never be covered and returns "".
• Shrinking while missing == 0 (instead of while the left character is a spare) removes a needed character and loses the window. Shrink only past characters with need < 0.
• Comparing full Counters on every step is correct but O(charset) per step; the missing counter makes the check O(1).

Related problems

• Minimum Size Subarray Sum (LeetCode 209): the same grow-then-shrink template with a numeric sum.
• Permutation in String (LeetCode 567): a fixed-size window that must match counts exactly.
• Longest Substring Without Repeating Characters (LeetCode 3): the “longest valid window” side of the pattern.