Minimum Window Substring
Expand until the window covers all required characters, then shrink while it still does.
Decision · step 2 of 25Substring Windows: Smallest window covering abc
r = 0, 'a' enters. It was still needed, so missing drops to 2.
What you will see
A frequency table beside the string; the window shrinks the moment coverage is met.
Cost
| Best | O(n) |
|---|---|
| Average | O(n + m) |
| Worst | O(n + m) |
| Space | O(alphabet) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Cells announce index, value and whether they are inside the window; each step announces the window bounds and the running value.
Reduced motion: The window frame snaps to its new bounds with a crossfade.
Before this
Taught by the same lesson
Substring Windows covers these too, in the same run.