visual walkthrough
Minimum Window Substring
The flagship Hard window problem; a Meta and Google classic.
The idea
Expand the right edge until the window contains every needed letter with enough copies. Then shrink from the left while it still does; every time it is valid, remember it if it is the shortest.
Both edges only move forward, so the whole scan is linear.
Complexity
| approach | time | space |
|---|---|---|
| Try every substring | O(n² · m) | O(m) |
| Sliding window | O(n + m) | O(m) |