Minimum Window Substring
Minimum Window Substring is a hard Sliding Window problem from the Blind 75. The key pattern is sliding window with need counts, and a good solution runs in O(|text| + |pattern|) time.
Problem
Return the shortest substring of text containing every character of pattern with multiplicity, or an empty string.
Examples
Example 1
Input
{"text":"ZXADOBECODEBANCY","pattern":"ABC"}Output
"BANC"Example 2
Input
{"text":"a","pattern":"a"}Output
"a"Example 3
Input
{"text":"a","pattern":"aa"}Output
""Approach
Expand the right edge until every required character is covered with multiplicity, then shrink the left edge as far as coverage allows and record the shortest window.
| Pattern | Sliding window with need counts |
|---|---|
| Time | O(|text| + |pattern|) |
| Space | O(alphabet) |
Watch out for
Repeated pattern letters must be matched as many times as they appear; return an empty string when no window exists.