Minimum Window Substring

This is the hardest of the standard window problems and a regular in senior interviews. Everything in it has appeared before: a count map, the shortest-window template, and a counter that avoids comparing whole maps. The difficulty is keeping those three pieces exactly in step.

The problem

Given strings s and t, return the shortest contiguous substring of s that contains every character of t, including repeats. If there is none, return the empty string. If several shortest ones exist, return the one that starts first.

• s = "AXBYCABZ", t = "ABC" → "CAB". It holds one A, one B and one C in three characters; nothing shorter does.
• s = "A", t = "AA" → "". t needs two As and s has only one.

Constraints: 1 ≤ lengths ≤ 10⁵; upper- and lowercase English letters.

Clarifying questions

• Do repeats in t count? Yes. t = "AAB" needs two As in the window.
• Case-sensitive? Yes: a and A are different.
• Which answer if several are shortest? Assume the leftmost; the code below keeps the first one it finds.

Approach 1: every start, grow until it covers t

For each start, extend the end until the window has enough of every character of t. That is the shortest window for this start, so stop there.

1from collections import Counter234def min_window_brute(s: str, t: str) -> str:5    """Every start, grow until the window covers t: O(n^2 * |alphabet|)."""6    if not t:7        return ""8    need = Counter(t)9    best = ""10    for start in range(len(s)):11        have: Counter[str] = Counter()12        for end in range(start, len(s)):13            have[s[end]] += 114            if all(have[c] >= n for c, n in need.items()):15                if not best or end - start + 1 < len(best):16                    best = s[start:end + 1]17                break18    return best

Time: O(n² · d), where d is the number of distinct characters in t, because each check loops over need. At n = 10⁵ that is over 10¹⁰ operations.

The key insight

Two ideas turn this into one pass.

It is a shortest window. Once a window covers t, making it longer keeps it covering t. So the rule "covers t" only gets easier as the window grows, and the shortest-window template applies: expand end until the window is valid, then shrink start while it is still valid, recording each valid length, until it breaks.

Validity must be O(1). Comparing two count maps each step costs O(d). Instead keep one integer, formed: how many distinct characters of t currently have enough copies in the window. The window covers t exactly when formed == required, where required is the number of distinct characters in t.

formed changes only at exact boundary crossings:

• When a character enters and its count becomes equal to what t needs, formed goes up by one. Going from 2 to 3 copies when only 1 is needed changes nothing.
• When a character leaves and its count drops below what t needs, formed goes down by one.

Approach 2: shrink while valid, with formed

1from collections import Counter234def min_window(s: str, t: str) -> str:5    """Shortest substring of s containing every character of t (with repeats)."""6    if not s or not t:7        return ""8    need = Counter(t)9    required = len(need)             # distinct characters that must be satisfied10    formed = 0                       # how many of them currently are11    have: dict[str, int] = {}12    start = 013    best_len = float("inf")14    best_start = 015    for end, char in enumerate(s):16        have[char] = have.get(char, 0) + 117        if char in need and have[char] == need[char]:18            formed += 119        while formed == required:    # valid: record, then try a shorter window20            if end - start + 1 < best_len:21                best_len = end - start + 122                best_start = start23            leaving = s[start]24            have[leaving] -= 125            if leaving in need and have[leaving] < need[leaving]:26                formed -= 1          # this requirement just broke27            start += 128    return "" if best_len == float("inf") else s[best_start:best_start + best_len]

Dry run on s = "AXBYCABZ", t = "ABC" (required = 3):

The answer is "CAB". Notice that removing X and Y never touched formed: they are not in t.

Time: O(|s| + |t|). Building need is O(|t|); each index of s enters once and leaves at most once. Space: O(d) for the two maps, where d is the number of distinct characters (at most 52 here).

Edge cases

• t longer than s, or no valid window. formed never reaches required, best_len stays infinite, and the function returns "".
• Repeats in t. For t = "AAB", need["A"] = 2, so formed counts A only when the second A enters, and uncounts it as soon as one leaves.
• Characters not in t. They go into have but never change formed. (You can skip counting them at all; it saves a little memory.)
• s equals t. The first valid window is the whole string, and removing any character breaks it.

Follow-ups

• "Return only the length." Return best_len, or 0 if it stays infinite.
• "t's characters must appear in order (a subsequence, not a multiset)." No longer a count window; it needs a two-pointer scan forward and backward, or dynamic programming (Minimum Window Subsequence).
• "s is huge and t is tiny." Filter s first to the positions whose character is in t, then run the same window over that shorter list of (index, character) pairs.