Pattern Guide
String Window Patterns
"Minimum window substring, anagram in string, longest with K distinct chars."
String sliding window problems maintain a window [l, r] over a string satisfying some character-frequency constraint. Core pattern: expand right to include new characters, shrink left when constraint violated. Key: track "satisfied" characters separately from total character counts to know when window is valid. Applications: minimum window containing all target chars, find all anagrams, longest substring with K distinct, max vowels in window.
Problems you can solve with this pattern
4 problems · click any to start solving
function minWindow(s, t) {
const need = new Map();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let have = 0, required = need.size; // need.size = distinct chars needed
const window = new Map();
let [l, minLen, minStart] = [0, Infinity, 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++; // met this char's need
while (have === required) { // valid window — try to shrink
if (r - l + 1 < minLen) { minLen = r - l + 1; minStart = l; }
const lc = s[l++];
window.set(lc, window.get(lc) - 1);
if (need.has(lc) && window.get(lc) < need.get(lc)) have--;
}
}
return minLen === Infinity ? '' : s.slice(minStart, minStart + minLen);
}Minimum window substring pattern: maintain freq maps for target and current window. Track "formed" = count of characters meeting target frequency. When formed == required (all chars satisfied), try shrinking left. Anagram finding: fixed-size window, compare char counts. Longest with K distinct: shrink when distinct count exceeds K. At most K distinct chars: shrink when window has > K unique chars.
function minWindow(s, t) {
const need = new Map();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let have = 0, required = need.size; // need.size = distinct chars needed
const window = new Map();
let [l, minLen, minStart] = [0, Infinity, 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++; // met this char's need
while (have === required) { // valid window — try to shrink
if (r - l + 1 < minLen) { minLen = r - l + 1; minStart = l; }
const lc = s[l++];
window.set(lc, window.get(lc) - 1);
if (need.has(lc) && window.get(lc) < need.get(lc)) have--;
}
}
return minLen === Infinity ? '' : s.slice(minStart, minStart + minLen);
}1. Build need map from target
2. Expand right: add char to window, increment
have if meets need3. When
have == required: record answer, shrink left, decrement have if drops below need"Formed" counter trick: Instead of comparing entire frequency maps each step (O(26)), track a single integer
have = number of distinct chars meeting their required count. When have == required, window is valid. O(1) check.Fixed-size window for anagrams: When window size is fixed (= pattern length), just slide without inner while loop. Compare frequency signatures at each step.