Minimum Window Substring

Problem

Given two strings s and t, find the shortest contiguous substring of s that contains every character of t, respecting multiplicity (if t has two 'a's, the window must contain at least two 'a's). Return that substring; if no window of s covers all of t, return the empty string "". The test data guarantees the answer is unique when it exists.

Examples

• s = "ADOBECODEBANC", t = "ABC" → "BANC" — the windows containing {A, B, C} include "ADOBEC" (length 6) and "BANC" (length 4); the shortest is "BANC".
• s = "a", t = "a" → "a" — the whole string is the (only) valid window.
• s = "a", t = "aa" → "" — t needs two 'a's but s only has one, so no window is valid.

Constraints

• 1 <= len(s), len(t) <= 10^5
• s and t consist of uppercase and lowercase English letters.
• The 10^5 bound demands an O(n)-ish algorithm — anything that re-examines O(n) windows at O(n) cost each is too slow.

Think about it first

TL;DR

Expand/contract sliding window with a have/need satisfaction counter — O(len(s) + len(t)) time, O(alphabet size) space.

Approach 1 — Brute force (grow from every start)

For each start index i, extend the end index until the window contains all of t, then record its length. Checking containment incrementally per start still means every start pays up to O(n) work.

from collections import Counter

def minWindow(s: str, t: str) -> str:
    n = len(s)
    need = Counter(t)
    required = len(need)
    best = ""
    for i in range(n):
        window: Counter = Counter()
        formed = 0
        for j in range(i, n):
            c = s[j]
            window[c] += 1
            if c in need and window[c] == need[c]:
                formed += 1
            if formed == required:
                if best == "" or j - i + 1 < len(best):
                    best = s[i:j + 1]
                break
    return best

Complexity: O(n²) time in the worst case, O(alphabet size) space.

With n = 10^5, n² = 10^10 window-character examinations — hopeless under the constraints.

Approach 2 — Sliding window with a satisfaction counter

Validity is monotone: extending a valid window keeps it valid, and shrinking an invalid one keeps it invalid. So a single pair of pointers suffices. Advance right until the window first becomes valid, then advance left while validity survives (each position of left here gives the best window ending at this right), then resume advancing right. Each pointer only moves forward, so the total work is O(n).

To make each validity test O(1), keep have = the number of distinct characters of t whose required multiplicity is currently met; the window is valid iff have == need_kinds.

flowchart TD
    A[Advance right, add s at right to window] --> B{have == need_kinds?}
    B -- No --> A
    B -- Yes --> C[Record window if shorter than best]
    C --> D[Remove s at left, advance left]
    D --> B

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if len(t) > len(s):
        return ""
    need = Counter(t)
    need_kinds = len(need)
    window: Counter = Counter()
    have = 0
    best_len = float("inf")
    best_left = 0
    left = 0

    for right, c in enumerate(s):
        window[c] += 1
        if c in need and window[c] == need[c]:
            have += 1

        while have == need_kinds:               # valid: try to shrink
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_left = left
            d = s[left]
            window[d] -= 1
            if d in need and window[d] < need[d]:
                have -= 1
            left += 1

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

Walkthrough with s = "ADOBECODEBANC", t = "ABC" (need = {A:1, B:1, C:1}):

1. right sweeps 0→5 (A D O B E C): after C at index 5, have = 3 — the window "ADOBEC" is the first valid one. Best length = 6 (best_left = 0). Shrinking pops A (index 0), which makes A deficient → have = 2, left = 1. Back to expanding.
2. right sweeps 6→10 (O D E B A): index 9 adds a second B, and the A at index 10 restores have = 3. Now the window is "DOBECODEBA" (left = 1, length 10).
3. Shrink: popping D, O, B, E keeps the window valid (the B at index 3 is covered by the spare B at index 9). Lengths seen: 10, 9, 8, 7, 6 — none beats the current best of 6 (ties don’t update). Popping the C at index 5 finally breaks validity → have = 2, left = 6.
4. right = 11 (N): nothing changes. right = 12 (C): have = 3 with window "ODEBANC" (left = 6, length 7). Shrinking pops the surplus O, D, E: lengths 7, 6, 5, 4 — the last two set new bests, ending at best_left = 9, best_len = 4 → "BANC". Popping the B at index 9 breaks validity; the sweep ends.

Result: "BANC".

Complexity: O(len(s) + len(t)) time — right and left each traverse s once — and O(alphabet size) space (at most 52 distinct keys). This is the classic two-pointer / expand-contract sliding window, made linear by the monotone validity predicate.

Approach 3 — Filtered sliding window

Characters not in t can never affect validity; they only get skipped over one at a time. Pre-extract the positions of s whose character occurs in t, and slide the window over that (possibly much shorter) list instead. Same worst-case complexity, but when t’s characters are rare in s the pointers touch far fewer elements.

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if len(t) > len(s):
        return ""
    need = Counter(t)
    need_kinds = len(need)
    filtered = [(i, c) for i, c in enumerate(s) if c in need]

    window: Counter = Counter()
    have = 0
    best_len = float("inf")
    best_left = 0
    left = 0

    for right in range(len(filtered)):
        c = filtered[right][1]
        window[c] += 1
        if window[c] == need[c]:
            have += 1

        while have == need_kinds:
            start = filtered[left][0]
            end = filtered[right][0]
            if end - start + 1 < best_len:
                best_len = end - start + 1
                best_left = start
            d = filtered[left][1]
            window[d] -= 1
            if window[d] < need[d]:
                have -= 1
            left += 1

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

Walkthrough with s = "ADOBECODEBANC", t = "ABC": the filtered list is [(0,A), (3,B), (5,C), (9,B), (10,A), (12,C)] — 6 entries instead of 13 characters. The expand/contract loop from Approach 2 now moves directly between meaningful positions: validity first arrives at (5,C) giving window 0..5 ("ADOBEC"), and the final contraction at (12,C) lands on (9,B)..(12,C) → "BANC".

Complexity: O(len(s) + len(t)) time (the filter pass dominates), O(len(s)) extra space for the filtered list.

Common pitfalls

• Comparing window == need on whole Counters every step — that re-introduces an O(alphabet) factor and, done naively with >= on all keys, an easy source of TLE; keep the have integer instead.
• Counting every occurrence toward have instead of only the transition window[c] == need[c] — extra copies of a character must not increment have twice.
• Forgetting multiplicity: t = "aa" needs two 'a's; a set-based check silently accepts one.
• Returning the best length but slicing with stale pointers — record best_left at the moment the best length is found, not left at the end.

Pattern takeaway

This is the variable-size sliding window archetype: when the predicate “window is good” is monotone under growth, two pointers that only move forward enumerate the best window for every right endpoint in linear total time. The auxiliary trick — an integer counting how many requirements are fully met — is what keeps each step O(1), and it reappears in almost every counting-window problem.