Minimum Window Substring

Minimum Window Substring is the classic "hard" sliding-window problem. It teaches the two-phase window: grow until valid, shrink while valid — and a counter trick to check validity in O(1).

The slow way first

The brute force: try every possible substring of s, and for each one check whether it covers t. There are O(n²) substrings, and each check costs O(n), so this is O(n³) — hopeless for long strings.

The question to ask: can I slide a window across s once, instead of re-checking every substring from scratch? Yes — and the key is tracking, in O(1), how close the current window is to being valid.

The idea: grow to satisfy, shrink to minimize

Keep a window [L, R]. Build a need count of every character in t, and a single number missing = how many characters of t are still uncovered.

• Grow R: extend the window one character at a time. Each time we add a character that t still needs, missing drops by one.
• When missing == 0 the window is valid — it covers all of t. Record it if it is the smallest so far, then shrink L to make it smaller.
• Shrink L: drop characters from the left as long as the window stays valid. The moment removing a character breaks validity, stop and go grow R again.

The whole window never moves backward: L and R each only travel left-to-right across s, so the total work is O(n).

Walk through it

Step through the animation. R races right until the window "ADOBEC" first covers A, B and C — that is our first valid window (length 6), so we record it. Then L shrinks: dropping the A breaks validity, so R grows again. We repeat this grow/shrink dance. Eventually the window tightens to "BANC" (length 4), beating 6, and that becomes the answer.

Pseudocode

need = count of each character in t
missing = len(t)                      # chars still uncovered
best = ""
L = 0
for R, ch in s:
    if t still needs ch: missing -= 1
    need[ch] -= 1
    while missing == 0:               # window [L..R] is valid
        if best is "" or window is smaller: best = s[L..R]
        need[s[L]] += 1               # give the left char back
        if need[s[L]] > 0: missing += 1   # window just broke
        L += 1
return best

The Python solution

def min_window(s, t):
    need = Counter(t)
    missing = len(t)
    best = ""
    L = 0
    for R, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:            # window is valid
            if best == "" or R - L + 1 < len(best):
                best = s[L:R + 1]
            need[s[L]] += 1
            if need[s[L]] > 0:
                missing += 1           # window broke
            L += 1
    return best

• need is a Counter of t; it can go negative for characters the window has in excess, which is exactly what makes the shrink check work.
• missing is the single source of truth for validity: missing == 0 means every required character is covered.
• We only decrement missing when need[ch] > 0 — i.e. the character was still actually required, not a surplus.
• The inner while does all the shrinking. We record best first, then pop the left character; if its count climbs back above 0, the window broke and we leave the loop.

Complexity

Space is O(k) where k is the number of distinct characters in t (the size of the counter). The time win is enormous: O(n³) → O(n), because each pointer only moves forward.

When this pattern shows up

Practice