Minimum Window Substring
Find the smallest substring of s that contains every character of t, including duplicates.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Expand the window to the right until it covers all counts from t, then shrink it from the left while it stays valid, recording the smallest window.
Pattern: Two pointers & sliding window. Move two indices through a sequence so each element is visited a constant number of times.
Complexity
| Measure | Bound |
|---|---|
| Time | O(|s| + |t|) |
| Extra space | O(alphabet) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.