Minimum Window Substring
The Prompt
Given two strings `s` and `t`, return the minimum window in `s` which will contain all the characters in `t`. If there is no such window in `s` that covers all characters in `t`, return the empty string `""`.
Understanding the Problem
You need the shortest slice of s containing every character of t, multiplicity included. Testing all substrings is hopeless; the workable framing is a window with a debt ledger: countT says what you owe, a window map says what you hold, and have counts how many distinct characters are fully paid off (have == need means the window covers t).
The rhythm is expand-then-contract: push right until the window is valid, then pull left as far as possible while it stays valid — that left-most valid position is the best window ending at this right.
The Interview Flow
Interviewer
This is a tough one. Given two strings, S and T, find the minimum window in S which contains all the characters in T, including duplicates.
Candidate
This is a classic sliding window problem. First, I need a way to track the required characters from T. A hash map is perfect for storing the character frequencies of T.
Interviewer
Good start. How do you apply the sliding window?
Candidate
I'll use two pointers, `left` and `right`. I expand the window by moving `right`. When the character `s[right]` is one of the required characters from T, I decrement its count in my tracker. I also need to track how many of the required characters I have satisfied.
Interviewer
Let's say you have two variables: `have` (characters satisfied) and `need` (total unique characters in T). When does the window become "valid"?
Candidate
The window is valid when `have` equals `need`. At this point, I have a potential answer. I'll record its length and starting position if it's the smallest one found so far. Now, I need to shrink the window from the left to see if I can find an even smaller valid window.
Interviewer
How do you shrink the window?
Candidate
I move the `left` pointer. If the character `s[left]` was a required character, I increment its count in my frequency map. If its count was zero before incrementing, it means I'm now missing a required character, so my `have` count decreases. The window is no longer valid, and I go back to expanding with the `right` pointer.
Interviewer
This process of expanding and contracting the window will find the minimum substring. Excellent. Please code it.
Why does expand-then-contract find the minimum?
The invariant: whenever have == need, the window contains all of t; the inner while-loop then shrinks until removing one more left character would break coverage. So for every right index, the algorithm measures the shortest valid window ending there — and the global minimum must be one of those, so it cannot be missed.
Each character is added by right once and removed by left at most once, and the have/need counters make each validity check O(1) instead of rescanning maps. Total: O(|s| + |t|) time, O(alphabet) space.
Optimal Sliding Window Approach
- If `t` is empty, return "". Create a frequency map `countT` for the characters in `t`.
- Initialize a window frequency map `window`. Initialize `have = 0` and `need` to the number of unique characters in `t`.
- Initialize `res` to store the result indices and `resLen` to infinity.
- Use a `left` pointer, and iterate through `s` with a `right` pointer.
- Add `s[right]` to the `window` map. If `s[right]` is in `countT` and `window[s[right]] == countT[s[right]]`, increment `have`.
- Once `have == need`, the window is valid. Now, try to shrink it.
- Inside a while loop (`have == need`): check if the current window is smaller than `resLen`. If so, update `res` and `resLen`.
- Then, shrink the window by moving `left`. Remove `s[left]` from the `window` map. If `s[left]` is in `countT` and its count in `window` just fell below its required count, decrement `have`. Increment `left`.
- After the main loop, if `resLen` is still infinity, no window was found. Otherwise, return the substring defined by the `res` indices.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function minWindow(s, t) {
if (t === "") return "";
const countT = {};
for (const char of t) {
countT[char] = (countT[char] || 0) + 1;
}
const window = {};
let have = 0;
const need = Object.keys(countT).length;
let res = [-1, -1];
let resLen = Infinity;
let left = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
window[char] = (window[char] || 0) + 1;
if (char in countT && window[char] === countT[char]) {
have++;
}
while (have === need) {
if ((right - left + 1) < resLen) {
res = [left, right];
resLen = right - left + 1;
}
const leftChar = s[left];
window[leftChar]--;
if (leftChar in countT && window[leftChar] < countT[leftChar]) {
have--;
}
left++;
}
}
const [l, r] = res;
return resLen !== Infinity ? s.substring(l, r + 1) : "";
}Explanation
Trace s = "AABCBCA", t = "ABC" — need = 3 distinct characters; the answer is "ABC".
1r expands to 3: the window "AABC" now holds A, B, and C, so have = 3 = need — first valid window, length 4. Time to shrink.
2Drop s[0] = A: the window still has one A, so it stays valid — "ABC", length 3, the new best. Dropping s[1] = A would leave zero As, so have falls to 2 and shrinking stops.
3r reaches 6 (an A) and the window is valid again; shrinking settles at "BCA", length 3 — a tie, not an improvement. Answer: "ABC".
Complexity Analysis
TIME
O(n)
SPACE
O(m)
Finished working through this one?
Mark it complete to track it on your Data Structures path.