ASAPUtils
The signal
Shortest contiguous window satisfying a containment constraint. The window shape is familiar; two things make this the hard one:
- The validity test — “does the window contain all of
t, with multiplicities?” — is expensive if you do it naively. - You’re minimising, which inverts where the shrinking and recording happen.
Approach ladder
1. Brute force — O(n² · m)
Every substring, checked against t’s counts. Correct, hopeless.
2. Window with a full count comparison — O(n · k)
Slide a variable window, and at each step compare the whole count map against t’s. Better, still
paying O(k) per step for a question that barely changed.
3. The insight — collapse validity to one integer
Keep two numbers:
need= the number of distinct characters int.satisfied= how many of those characters currently appear in the window at least as many times as required.
The window is valid exactly when satisfied === need. An O(k) comparison becomes an O(1) integer
check.
The delicate part is updating satisfied. It changes only at the crossing point:
- when adding a character makes its window count equal its requirement →
satisfied++ - when removing a character makes its window count fall below its requirement →
satisfied--
Incrementing on every relevant add would let duplicates inflate the counter and declare the window valid too soon. This is the bug in this problem.
4. Optimal — O(n + m)
string minWindow(string s, string t) {
if (t.empty() || s.size() < t.size()) return "";
unordered_map<char,int> want, have;
for (char c : t) want[c]++;
int need = want.size(), satisfied = 0, l = 0;
int bestLen = INT_MAX, bestL = 0;
for (int r = 0; r < (int)s.size(); r++) {
have[s[r]]++;
if (want.count(s[r]) && have[s[r]] == want[s[r]]) satisfied++;
while (satisfied == need) {
if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
have[s[l]]--;
if (want.count(s[l]) && have[s[l]] < want[s[l]]) satisfied--;
l++;
}
}
return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}
function minWindow(s, t) {
if (!t.length || s.length < t.length) return '';
const want = new Map(), have = new Map();
for (const c of t) want.set(c, (want.get(c) ?? 0) + 1);
let need = want.size, satisfied = 0, l = 0;
let bestLen = Infinity, bestL = 0;
for (let r = 0; r < s.length; r++) {
have.set(s[r], (have.get(s[r]) ?? 0) + 1);
if (want.has(s[r]) && have.get(s[r]) === want.get(s[r])) satisfied++;
while (satisfied === need) {
if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
have.set(s[l], have.get(s[l]) - 1);
if (want.has(s[l]) && have.get(s[l]) < want.get(s[l])) satisfied--;
l++;
}
}
return bestLen === Infinity ? '' : s.slice(bestL, bestL + bestLen);
}
Maximise vs minimise — the inversion
Put the two side by side, because this is the transferable lesson:
| Longest valid window | Shortest valid window | |
|---|---|---|
| Shrink while | invalid | valid |
| Record | after the shrink loop | inside the shrink loop |
| Goal | grow as much as allowed | squeeze as small as possible |
Same skeleton, opposite condition, different recording point. Mixing them produces code that looks right and returns nonsense — which is exactly what makes this a hard problem rather than a medium one.
Complexity
- Time O(n + m) — each pointer traverses
sonce; buildingwantis O(m). - Space O(k) — k distinct characters across
sandt.
Traps
- Incrementing
satisfiedon every add rather than only at the crossing. Duplicates break it. - Recording after the shrink loop. By then the window is already invalid.
- Returning the length instead of the substring. Track
bestLtoo. tlonger thans, or empty. Guard both.
Blank re-solve prompt
Return the shortest substring of s containing all characters of t with multiplicity, in O(n). Get the satisfied counter right without looking.