Minimum Window Substring: The Hard Sliding Window Boss

"Minimum Window Substring" is a Hard-level staple in Meta, Amazon, LinkedIn loops, and it is a textbook fit for the Sliding Window pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 9 of 11 in the Sliding Window arc.

The Problem

Given strings s and t, return the minimum window of s containing every character of t including multiplicities, or an empty string if none exists. The answer is guaranteed unique. This is the archetypal hard window question and a recurring Meta onsite.

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

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Minimum window covering a multiset is the covering flavor of the pattern: expand until the window covers t, then shrink from the left while coverage holds, recording the tightest span. The trick is testing coverage in O(1), not by comparing histograms.

The Approach

Keep need (counts of t) and a single integer formed — how many distinct characters currently meet their required count. Increment formed only when a character's window count reaches its need; decrement when it drops below during shrinking. Coverage is just formed == len(need).

Expand right unconditionally; on coverage, shrink left as far as possible, updating the best span. Every index enters and leaves once — O(n) despite the nested loop, and saying amortized out loud is expected at this level.

Python Solution

def min_window(s: str, t: str) -> str:
    """Smallest window of s covering all characters of t with multiplicity."""
    if not t or len(t) > len(s):
        return ""

    from collections import Counter
    need = Counter(t)
    window: dict[str, int] = {}
    formed = 0
    best = (float("inf"), 0, 0)      # (length, left, right)
    left = 0

    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            formed += 1
        while formed == len(need):
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            out = s[left]
            window[out] -= 1
            if out in need and window[out] < need[out]:
                formed -= 1
            left += 1

    length, i, j = best
    return "" if length == float("inf") else s[i : j + 1]

Complexity

• Time: O(n + m) — each index of s enters and leaves the window once; building need is O(m)
• Space: O(m + alphabet) — the need and window maps

Interview Tips and Follow-Ups

• The formed counter is the entire interview: comparing full histograms per step is O(26·n) and reads as not knowing the trick.
• Multiplicity matters — t = "aa" requires two a's. Tests that ignore this pass on wrong solutions.
• Store the best window as indices, not a sliced string — slicing per improvement is accidental O(n²) in the worst case.

If this clicked, continue the Sliding Window arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.