Patterns/Part V - Strings, Sequences & Grid/String Window Patterns

Pattern Reference

String Window Patterns

"Sliding window applied to strings: anagram substrings, min window substring, substring concatenation."

Loading...

Deep Dive Tutorial

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.

Minimum window substring template
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);
}

Worked Problems

1
Minimum Window Substring
Hard
Solve ↗
2
Find All Anagrams in a String
Medium
Solve ↗
3
Longest Substring with At Most K Distinct Characters
Medium
Solve ↗
4
Fruit Into Baskets
Medium
Solve ↗
frame
String window template (memorize):
1. Build need map from target
2. Expand right: add char to window, increment have if meets need
3. 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.
← All Patterns