0
L
Given strings s and t, find the shortest contiguous substring of s that contains every character of t (with multiplicity). A two-pointer sliding window with a need / have counter finds it in O(|s| + |t|) time.
Given s = "ADOBECODEBANC" and t = "ABC", return the shortest window in s that contains 'A', 'B', and 'C'. Answer: "BANC". If no such window exists, return "". Characters in t may repeat (e.g. t="AA" requires two As in the window).
[L..R] and two maps: what we need (from t) and what the current window has. A single integer have counts how many distinct characters have hit their required frequency. When have === required the window is valid — record it, then advance L to shrink it. You only ever need one pass over s.t; store required = need.size (distinct chars needed).s[R] to the window map. If its count just reached the required amount, increment have.have === required. Record the window if it's the smallest so far, then remove s[L] from the window map. If that drops the count below its requirement, decrement have. Advance L.s at the saved best indices, or "" if no valid window was ever found.have on every match instead of only when the window count exactly reaches the required count. If t = "AA"you need two A's; adding a third A to the window must not increment have again — window.get(c) === need.get(c) handles this precisely.Space is O(|Σ|)— at most the size of the character alphabet for the two maps. In the worst case (all distinct chars) that's O(|s| + |t|) but bounded by the alphabet.
need map from t="ABC": A:1, B:1, C:1. need 3 distinct chars. Start L=R=0.function minWindow(s: string, t: string): string {
if (t.length === 0) return '';
// Build the "need" map: how many of each t-char we require
const need = new Map<string, number>();
for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
const required = need.size; // distinct chars we must satisfy
const window = new Map<string, number>(); // current window counts
let have = 0; // distinct chars currently satisfied
let L = 0;
let bestLen = Infinity;
let bestL = 0, bestR = 0;
for (let R = 0; R < s.length; R++) {
// 1. Expand: add s[R] to the window
const c = s[R];
window.set(c, (window.get(c) ?? 0) + 1);
if (need.has(c) && window.get(c) === need.get(c)) {
have++; // this char's count just hit its requirement
}
// 2. Contract: shrink from the left while window is valid
while (have === required) {
const len = R - L + 1;
if (len < bestLen) { bestLen = len; bestL = L; bestR = R; }
const lc = s[L];
window.set(lc, window.get(lc)! - 1);
if (need.has(lc) && window.get(lc)! < need.get(lc)!) {
have--; // we dropped below requirement; window invalid
}
L++;
}
}
return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);
}t tallies how many of each character we require. required = need.size is the number of distinct characters we must satisfy — not t.length.window mirrors the need map but for the current window. have counts how many distinct chars are currently satisfied. Both pointers start at 0; bestLen = Infinity so any valid window beats it.R, add s[R] to the window. Crucially, only increment have when the window count exactly equalsthe required count — extra copies don't count again.while loop runs as long as the window is valid. Record the current window size; then remove s[L], decrement have if needed, and advance L. This greedily produces the smallest valid window before the window becomes invalid again.bestLen is still Infinity no window was ever valid → return "". Otherwise slice the saved indices. Note bestR + 1 is exclusive in slice.|s| steps, and building the need map is O(|t|). O(|Σ|) space for the two maps (bounded by alphabet size).need map stores the count (2), and have only increments when window.get(c) === need.get(c). No special case needed.have since need.has(c) is false.bestLen during the record step, instead of only keeping the first one.s to only the characters that appear in t, reducing the effective length of s to at most |t| × k.| "shortest / smallest window containing …" | expand-right / contract-left sliding window |
| must contain all chars of t (with multiplicity) | need map + have/required counter |
| increment have only when count exactly hits requirement | window.get(c) === need.get(c) |
| "permutation in string" / "find all anagrams" | same template, fixed-size window variant |
const need = new Map<string, number>();
for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
const required = need.size;
const window = new Map<string, number>();
let have = 0, L = 0, bestLen = Infinity, bestL = 0, bestR = 0;
for (let R = 0; R < s.length; R++) {
const c = s[R];
window.set(c, (window.get(c) ?? 0) + 1);
if (need.has(c) && window.get(c) === need.get(c)) have++;
while (have === required) {
if (R - L + 1 < bestLen) { bestLen = R - L + 1; bestL = L; bestR = R; }
const lc = s[L];
window.set(lc, window.get(lc)! - 1);
if (need.has(lc) && window.get(lc)! < need.get(lc)!) have--;
L++;
}
}
return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);minWindow(s, t)?t = "AA", when should have be incremented for character 'A'?have?s="ADOBECODEBANC", t="ABC", what is the minimum window?