Problem 10 · Two Pointers & Sliding Window

Minimum Window Substring

HardClassic DSA & systems

01Problem

Given strings s and t, return the smallest substring of s that contains every character of t (with multiplicity), or an empty string.

02Key insight

Expand right until the window satisfies t, then shrink left while it still does. Track a single 'missing' counter so validity checks are O(1) rather than comparing maps.

03Solution

solution.pypython21 lines

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not t or not s:
        return ""
    need = Counter(t)
    missing = len(t)
    left = 0
    best_start, best_len = 0, float("inf")
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return "" if best_len == float("inf") else s[best_start:best_start + best_len]

Try it first.

TimeO(|s| + |t|)

SpaceO(alphabet)

tests.py · 4 passing

tests.pypython4 lines

assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "a") == "a"
assert min_window("a", "aa") == ""
assert min_window("aa", "aa") == "aa"

04Staff-level follow-up

If t is small but s is huge and only few chars matter? Pre-filter s to (index, char) pairs for chars in t and slide over that list, cutting work when s is mostly irrelevant characters.