Minimum Window Substring
HardSliding window
Given two strings s and t, return the shortest substring of s, a run of consecutive characters, that contains every character of t, each at least as many times as it appears in t.
Upper and lowercase letters are different characters. If no substring of s works, return the empty string "". If several shortest substrings tie, return any of them.
Examples
Input: s = "XAYBZCAB", t = "ABC" Output: "CAB"
CAB holds an A, a B and a C, and no shorter piece of s does.
Input: s = "aab", t = "aaa" Output: ""
s has only two a’s, and t needs three.
Constraints
1 ≤ s.length, t.length ≤ 10⁵sandtuse upper and lowercase English letters only.
Stuck?
Hint 1
Grow a window to the right until it holds everything t needs, then shrink it from the left for as long as it still does.
Hint 2
Count what t needs in a Map, and keep a number of characters still missing, so checking the window is O(1) instead of comparing every count.
The idea
Grow a window to the right until it holds everything t asks for, then shrink it from the left for as long as it still does. The shortest window is found this way, at the moment its left edge can move no further. A count of the characters still missing makes each check take constant time.
Time O(m + n)Extra space O(1): at most 52 letters counted
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
need starts as how many of each character t asks for. As the window takes characters in, their counts go down, and a count below zero means the window has spares.
function minWindow(s, t) { const need = new Map(); for (const c of t) { need.set(c, (need.get(c) || 0) + 1); } let missing = t.length; let start = 0; let bestStart = 0; let bestLength = Infinity; for (let end = 0; end < s.length; end++) { const added = s[end]; if (need.has(added)) { if (need.get(added) > 0) missing--; need.set(added, need.get(added) - 1); } while (missing === 0) { if (end - start + 1 < bestLength) { bestLength = end - start + 1; bestStart = start; } const removed = s[start]; if (need.has(removed)) { need.set(removed, need.get(removed) + 1); if (need.get(removed) > 0) missing++; } start++; } } return bestLength === Infinity ? '' : s.slice(bestStart, bestStart + bestLength);}The trap
Turning t into a Set keeps which characters it uses but forgets how many of each. When t repeats a character, a window holding a single copy is accepted as complete, so the answer comes out too short, or appears where there should be none. Starting a new scan from every position also makes it O(n²).
function minWindow(s, t) { const need = new Set(t); // which letters, not how many of each let best = ''; for (let start = 0; start < s.length; start++) { const seen = new Set(); for (let end = start; end < s.length; end++) { if (need.has(s[end])) seen.add(s[end]); if (seen.size === need.size) { if (!best || end - start + 1 < best.length) best = s.slice(start, end + 1); break; } } } return best;}