Minimum Window Substring
Hard Variable window with need counts
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the shortest substring of s that contains every character of t (with multiplicity). Return "" if none exists.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the shortest part of s containing all letters of t.
Why this works: expand until everything is covered, then shrink from the left while it stays covered. A single "missing" counter tells you when you're covered.
Example: s = "ADOBECODEBANC", t = "ABC"
first cover "ADOBEC" (6)keep sliding … "BANC" covers A, B, C (4)answer "BANC"
✦Hints open one at a time
↗Approach
need[c] starts as counts in t; missing = |t|. Moving right decrements need[c] and, if it was positive, missing. When missing == 0, record the window and shrink: increment need of the left char, and if it becomes positive, the window is no longer valid.
</>Solution (Java)
class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
for (int r = 0; r < s.length(); r++) {
if (need[s.charAt(r)]-- > 0) missing--; // a needed char arrived
while (missing == 0) {
if (r - left + 1 < bestLen) {
bestLen = r - left + 1;
bestStart = left;
}
if (++need[s.charAt(left++)] > 0) missing++; // we just lost a needed char
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
}!Common mistake
Comparing full count maps on every step — correct but much slower and error-prone.
- Time: O(|s| + |t|).
- Space: O(128).