Minimum Window Substring

hardTests passed 2026-11-11v1.0.0
TC: O(|S| + |T|)|SC: O(|T|)
Sliding WindowOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Maintain `have == need` count of distinct required characters from `t`. Expand `r` until `have == need`, then advance `l` aggressively while maintaining `have == need` and updating the smallest slice.

2. Complexity Bounds & Proof

Both `l` and `r` advance across `s` strictly monotonically at most once each.

3. Minimal Idiomatic Code

def minWindow(s: str, t: str) -> str:
    if not t: return ""
    need = Counter(t)
    window = {}
    have, req = 0, len(need)
    res_l, res_len = 0, float('inf')
    l = 0
    for r, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == req:
            if r - l + 1 < res_len:
                res_l, res_len = l, r - l + 1
            lc = s[l]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                have -= 1
            l += 1
    return "" if res_len == float('inf') else s[res_l:res_l + res_len]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Comparing `have == need` counts UNIQUE required characters meeting their quota, NOT total characters in `t`.
Follow-ups:- Filtered sliding window only visits indices of `s` that exist in `t` (huge speedup when `s` is mostly irrelevant text).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Longest Substring Without Repeating Characters (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.