AlgoScope

Minimum Window Substring

Expand until the window covers all required characters, then shrink while it still does.

Sliding window, algorithm, advanced
Right 0 is a, missing 2.window 0-0a0d1o2b3e4c5o6d7e8b9a10n11c12lr

Substring Windows: Smallest window covering abc

Decision, step 2 of 25

r = 0, 'a' enters. It was still needed, so missing drops to 2.

How substring windows works

Cost

Best
O(n)
Average
O(n + m)
Worst
O(n + m)
Space
O(alphabet)

Taught by the same lesson

Substring Windows covers these too, in the same run.