LeetCode 76 ·
Hard
Minimum Window Substring
Find the shortest substring of s containing every character of t (with multiplicity).
Try it
Step through the core mechanic. The simulator below runs the sliding window shape this problem is built on.
Interactive · Sliding-window walkthrough LC 3: longest substring without repeating characters
0
a
1
b
2
c
3
a
4
b
5
c
6
b
7
b
start: window is empty
window0 set{} best0
Why sliding window works.
The right edge always moves forward. The left edge only moves forward (never
back). Each character enters and leaves the window at most once, so the total
work is O(n) — even though the algorithm looks like a nested loop.
This "amortised linear" pattern is the core insight: a while-inside-a-for is
fine if the inner work is bounded by total movements, not per-iteration.
The approach
have/need counts plus a matched integer. Expand right until the window covers t, then shrink left while still valid, recording the smallest. matched moves only when a count just crosses its requirement.
| Aspect | Value |
|---|---|
| Pattern | Sliding window |
| Recognise it by | Smallest window covering all required characters. |
| Time complexity | O(n) |
| Space complexity | O(Σ) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.