Minimum Window Substring
Given strings s and t, return the shortest contiguous substring of s that contains every character of t with at least the required multiplicity. If no such window exists return the empty string.
- 1 ≤ s.length, t.length ≤ 10^5
- Uppercase and lowercase English letters
- Answer is unique if it exists
- *Shortest contiguous* substring
- Condition is about character counts that a window must cover
- Once a window is valid, shrinking from the left keeps looking for a better one
A question about contiguous ranges whose validity is monotonic (extending a valid window can only break it; shrinking an invalid window can only fix it) can be answered with two indices that both only move right. Each element enters and leaves the window once, giving O(n) instead of O(n^2) enumeration of subarrays.
Count the required characters of t. Expand the right end over s, decrementing the requirement for each character and tracking how many distinct characters are fully satisfied. Whenever every requirement is met, shrink from the left as far as possible while the window stays valid, recording the best length. Then advance the left one more step to break validity and continue expanding. Each character enters and leaves the window at most once.
- Checking every start position with a fresh count is O(n^2). Pre-filtering
sto only characters present intspeeds up the same algorithm whentis tiny relative tos.