Minimum Window Containing All Required Characters

Pattern: Sliding Window · Difficulty: Hard · Asked at: Meta, Amazon, Uber, LinkedIn

Classic version: LeetCode 76

Problem

Given strings s and t, return the shortest contiguous substring of s that contains every character of t, including duplicates (if t has two as the window needs two as). Return "" if no such window exists. If several windows tie for shortest, return the leftmost.

Examples

min_window("ADOBECODEBANC", "ABC") → "BANC"
min_window("a", "a")               → "a"
min_window("a", "aa")              → ""

Constraints

• 1 ≤ len(s), len(t) ≤ 10⁵, case-sensitive.
• Target: O(len(s) + len(t)).

Starter code

def min_window(s: str, t: str) -> str:
    pass

Hints

Where this shows up in data engineering

“Smallest time window in which all required event types occurred” (e.g. the shortest span that contains a login, a payment and a confirmation) is this problem over event logs. It also tests the key streaming idea: maintain an aggregate incrementally instead of recomputing it.

Solution

from collections import Counter

def min_window(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)                 # required chars not yet covered, with multiplicity
    left = 0
    best = (float("inf"), 0, 0)      # (length, start, end)
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1                # negative = surplus inside the window
        if missing == 0:
            # shrink while the leftmost char is surplus
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right + 1)
            # give up the leftmost required char to look for the next window
            need[s[left]] += 1
            missing += 1
            left += 1
    return s[best[1]:best[2]] if best[0] != float("inf") else ""

Tests

Your solution should pass these:

assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "a") == "a"
assert min_window("a", "aa") == ""
assert min_window("aa", "aa") == "aa"
assert min_window("ab", "b") == "b"
assert min_window("bba", "ab") == "ba"
assert min_window("cabwefgewcwaefgcf", "cae") == "cwae"

Explanation

State: need[c] = how many more c the window still needs (negative = surplus). missing = sum of the positive parts, so “window covers t” is just missing == 0, O(1) instead of comparing two counters.

Loop: extend right; once covered, drop surplus characters from the left (they can’t be needed), record the window, then deliberately drop one required character so the search continues for a shorter window further right.

Complexity: O(|s| + |t|) time: each index enters and leaves the window once. O(alphabet) space.

Pitfalls: forgetting multiplicity (using a set for t), comparing full counters on every step (O(|s|·alphabet)), and off-by-one when slicing the answer.

Follow-up questions