LeetCode 76 · Sliding Window · concept: sliding-window
Problem
Given strings s and t, return the shortest substring of s containing every character of t (with multiplicity). Empty string if none exists.
s = "ADOBECODEBANC", t = "ABC" -> "BANC"
Approach — expand to satisfy, contract to minimize (optimal)
The hardest sliding-window template: grow the right edge until the window is valid (contains all of t), then shrink the left edge as far as possible while staying valid, recording the smallest valid window seen.
from collections import Counter
def minWindow(s, t):
if not t or not s:
return ""
need = Counter(t)
missing = len(t) # total chars still needed (with multiplicity)
l = 0
best = (float("inf"), 0, 0) # (length, start, end)
for r, ch in enumerate(s):
if need[ch] > 0: # this char helps satisfy t
missing -= 1
need[ch] -= 1 # may go negative for surplus chars
while missing == 0: # window is valid -> try to shrink
if r - l + 1 < best[0]:
best = (r - l + 1, l, r)
need[s[l]] += 1
if need[s[l]] > 0: # removing s[l] breaks validity
missing += 1
l += 1
return "" if best[0] == float("inf") else s[best[1] : best[2] + 1]Time O(|s| + |t|), space O(|t|).
The two-phase rhythm
- Expand (
for r): always advance right, folding each char intoneed.missingcounts required chars not yet covered. - Contract (
while missing == 0): while valid, record the window and pull the left edge in; validity breaks precisely when you remove a char the window actually needed (need[s[l]] > 0after incrementing).
Letting need go negative for surplus characters is the trick that makes contraction correct — you only lose validity when a genuinely-needed char’s count would drop below required.
Key insight
“Smallest window containing a target set” → expand-to-valid, then contract-to-minimal. The missing/need bookkeeping (with negatives for surplus) generalizes to any “cover all requirements with the tightest window” problem — the canonical hard sliding window.
Related
- concept: sliding-window
- prev: Permutation in String · next: Sliding Window Maximum
Software engineering
Infrastructure & security
Computer science
Hardware & engineering