Minimum Window Substring
Problem statement
Given a string $S$ of length $m$ and a string $T$ of length $n$, find the shortest contiguous substring of $S$ that contains every character in $T$ (including duplicates). If no such substring exists, return the empty string. If there are multiple windows of the same minimum length, return the one that appears first (leftmost).
Constraints:
- $1 \le m, n \le 10^5$
- $S$ and $T$ consist of uppercase and lowercase English letters
- $T$ may contain duplicate characters, and the window must include at least that many copies of each
Example 1:
- Input: $S = $
"ADOBECODEBANC", $T = $"ABC" - Output:
"BANC" - Explanation: The substring
"BANC"starting at index 9 containsA,B, andCand has length 4. Earlier windows like"ADOBEC"(length 6) also contain all characters but are longer.
Example 2:
- Input: $S = $
"a", $T = $"a" - Output:
"a"
Example 3:
- Input: $S = $
"a", $T = $"aa" - Output:
"" - Explanation: $T$ requires two
as but $S$ only has one, so no valid window exists.
Design an algorithm that runs in $O(m + n)$ time.
Show hint
Which technique lets you examine every candidate substring without restarting from scratch each time the starting position changes?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.