TL;DR
Expand/contract sliding window with a have/need satisfaction counter — O(|s| + |t|) time, O(|alphabet|) space.
Approach 1 — Brute force (grow from every start)
For each start index i, extend the end index until the window contains all of t, then record its length. Checking containment incrementally per start still means every start pays up to O(n) work.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
n = len(s)
need = Counter(t)
required = len(need)
best = ""
for i in range(n):
window: Counter = Counter()
formed = 0
for j in range(i, n):
c = s[j]
window[c] += 1
if c in need and window[c] == need[c]:
formed += 1
if formed == required:
if best == "" or j - i + 1 < len(best):
best = s[i:j + 1]
break
return best
Complexity: O(n²) time in the worst case, O(|alphabet|) space.
With n = 10^5, n² = 10^10 window-character examinations — hopeless under the constraints.
Approach 2 — Sliding window with a satisfaction counter
The insight: validity is monotone — extending a valid window keeps it valid, shrinking an invalid one keeps it invalid. So a single pair of pointers suffices: push right until the window first becomes valid, then pull left in while validity survives (every position of left here is the best window ending at this right), then resume pushing right. Each pointer only moves forward, so the total work is O(n).
To make each validity test O(1), keep have = the number of distinct characters of t whose required multiplicity is currently met; the window is valid iff have == need_kinds.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(t) > len(s):
return ""
need = Counter(t)
need_kinds = len(need)
window: Counter = Counter()
have = 0
best_len = float("inf")
best_left = 0
left = 0
for right, c in enumerate(s):
window[c] += 1
if c in need and window[c] == need[c]:
have += 1
while have == need_kinds: # valid: try to shrink
if right - left + 1 < best_len:
best_len = right - left + 1
best_left = left
d = s[left]
window[d] -= 1
if d in need and window[d] < need[d]:
have -= 1
left += 1
if best_len == float("inf"):
return ""
return s[best_left:best_left + best_len]
Walkthrough with s = "ADOBECODEBANC", t = "ABC" (need = {A:1, B:1, C:1}):
right sweeps 0→5 (A D O B E C): after C at index 5, have = 3 — the window "ADOBEC" is the first valid one. Best length = 6 (best_left = 0). Shrinking pops A (index 0), which makes A deficient → have = 2, left = 1. Back to expanding.right sweeps 6→10 (O D E B A): index 9 adds a second B, and the A at index 10 restores have = 3. Now the window is "DOBECODEBA" (left = 1, length 10).- Shrink: popping
D, O, B, E keeps the window valid (the B at index 3 is covered by the spare B at index 9). Lengths seen: 10, 9, 8, 7, 6 — none beats the current best of 6 (ties don’t update). Popping the C at index 5 finally breaks validity → have = 2, left = 6.
right = 11 (N): nothing changes. right = 12 (C): have = 3 with window "ODEBANC" (left = 6, length 7). Shrinking pops the surplus O, D, E: lengths 7, 6, 5, 4 — the last two set new bests, ending at best_left = 9, best_len = 4 → "BANC". Popping the B at index 9 breaks validity; the sweep ends.
Result: "BANC".
Complexity: O(|s| + |t|) time — right and left each traverse s once — and O(|alphabet|) space (at most 52 distinct keys). This is the classic two-pointer / expand-contract sliding window: a linear scan over all O(n²) windows made possible by the monotone validity predicate.
Approach 3 — Filtered sliding window
The insight: characters not in t can never affect validity; they only get skipped over one at a time. Pre-extract the positions of s whose character occurs in t, and slide the window over that (possibly much shorter) list instead. Same worst-case complexity, but when t’s characters are rare in s the pointer walks touch far fewer elements.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(t) > len(s):
return ""
need = Counter(t)
need_kinds = len(need)
filtered = [(i, c) for i, c in enumerate(s) if c in need]
window: Counter = Counter()
have = 0
best_len = float("inf")
best_left = 0
left = 0
for right in range(len(filtered)):
c = filtered[right][1]
window[c] += 1
if window[c] == need[c]:
have += 1
while have == need_kinds:
start = filtered[left][0]
end = filtered[right][0]
if end - start + 1 < best_len:
best_len = end - start + 1
best_left = start
d = filtered[left][1]
window[d] -= 1
if window[d] < need[d]:
have -= 1
left += 1
if best_len == float("inf"):
return ""
return s[best_left:best_left + best_len]
Walkthrough with s = "ADOBECODEBANC", t = "ABC": the filtered list is [(0,A), (3,B), (5,C), (9,B), (10,A), (12,C)] — 6 entries instead of 13 characters. The expand/contract dance from Approach 2 now hops directly between meaningful positions: validity first arrives at (5,C) giving window 0..5 ("ADOBEC"), and the final contraction at (12,C) lands on (9,B)..(12,C) → "BANC".
Complexity: O(|s| + |t|) time (the filter pass dominates), O(|s|) extra space for the filtered list.
Common pitfalls
- Comparing
window == need on whole Counters every step — that re-introduces an O(alphabet) factor and, done naively with >= on all keys, an easy source of TLE; keep the have integer instead.
- Counting every occurrence toward
have instead of only the transition window[c] == need[c] — extra copies of a character must not increment have twice.
- Forgetting multiplicity:
t = "aa" needs two 'a's; a set-based check silently accepts one.
- Returning the best length but slicing with stale pointers — record
best_left at the moment the best length is found, not left at the end.
Pattern takeaway
This is the variable-size sliding window archetype: when the predicate “window is good” is monotone under growth, two pointers that only move forward enumerate the best window for every right endpoint in linear total time. The auxiliary trick — an integer counting how many requirements are fully met — is what keeps each step O(1), and it reappears in almost every counting-window problem.