Blind 75 Visualized

#16 · Sliding Window

Minimum Window Substring

Given strings s and t, return the shortest substring of s that contains every character of t (including duplicates). Return an empty string if no such window exists.

HardLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sliding window with a frequency table

A window [left, right] expands on the right until it contains everything t needs, then shrinks from the left while it still does. A table of required letter counts (decremented as letters enter, incremented as they leave) tracks what the window still lacks.

Memory layout

Two integers for the window plus a count table keyed by character: a hash map, or a flat 128/256-slot integer array for ASCII (one contiguous block, direct indexing, no hashing).

OperationCost
expand / shrink one stepO(1)
whole scanO(|s| + |t|)
extra spaceO(σ), σ = alphabet size

Single "missing" counter

Instead of comparing whole tables, keep one integer: how many required letters the window still lacks. Adding a needed letter decrements it; removing one that drops a count back above zero increments it. Valid exactly when it is 0.

Memory layout

One scalar next to the count table. It turns the validity test from O(distinct letters of t) into O(1).

OperationCost
is the window valid?O(1)
update on add / removeO(1)

Why it fits

  • Validity is monotone: if a window covers t, any larger window containing it does too, and any window that fails can only be fixed by growing. That monotonic structure is exactly what sliding windows exploit: one pass, never moving a pointer backwards.
  • Each index enters the window once and leaves at most once, so the total pointer movement is at most 2|s|, even though there is a while loop inside the for loop.
  • A signed counter table makes surplus letters visible as negative counts, which is what lets the window shrink past duplicates safely and track validity with a single integer.

Why alternatives degrade

All substrings, each tested:
O(n²) substrings, each checked in O(n) or O(|t|): up to O(n³). Even shortest-first brute force is O(n² · |t|).
Comparing two hash maps every step:
Correct, but each validity test costs O(distinct letters of t), multiplying the linear scan by that factor. A single missing counter removes it.
Sorting or two-pointer without a table:
The window needs letter multiplicities (duplicates in t), which only a count table can track in O(1) per step.

Four approaches, from naive to production

1 · beginner

Every window, shortest lengths first

time O(n² · |t|)space O(n) per window slice

Try all windows of length |t|, then |t| + 1, and so on. For each, count whether it contains every letter of t enough times; the first window that does is the shortest.

string minWindow(string s, string t) {
    auto covers = [&](const string& w) {
        int cnt[256] = {0};
        for (unsigned char c : t) cnt[c]++;
        for (unsigned char c : w) cnt[c]--;
        for (unsigned char c : t) if (cnt[c] > 0) return false;
        return true;
    };
    int n = s.size();
    for (int len = t.size(); len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            string window = s.substr(i, len);
            if (covers(window)) return window;
        }
    }
    return "";
}

Flaws & bottlenecks

  • Up to n²/2 windows, and each check re-counts letters from scratch (O(|t|) splits of an O(n) string).
  • Allocates a new substring for every candidate window.
  • The early exit helps only because lengths are tried in increasing order; if the answer is long, almost every window is tested first.

Interviewer cross-questions

Why does trying lengths in increasing order let you return early?

Say: The first covering window found at length L is a shortest one, since every shorter length was already tried without success. So no further search is needed. The price is that all shorter windows were fully tested.

Where is the repeated work?

Say: Neighbouring windows share almost all of their letters. Re-counting the whole window each time throws that away: moving the window one step changes only two letters. A sliding window with running counts exploits this.

How do you handle duplicates in t?

Say: The check compares counts, not just presence: a window must hold each letter at least as many times as t does (A×2 needs two A's). Using sets would wrongly accept a single A.

2 · intermediate

Sliding window, recheck all letters each time

time O(|s| · σ_t)space O(σ)

Slide a window: add letters on the right, and while the window covers t (checked by comparing counts for every distinct letter of t) record it and shrink from the left.

string minWindow(string s, string t) {
    unordered_map<char, int> need;
    for (char ch : t) need[ch]++;
    unordered_map<char, int> have;
    auto satisfied = [&]() { for (auto& [ch, n] : need) if (have[ch] < n) return false; return true; };
    int bestStart = 0;
    int bestLen = INT_MAX;
    int left = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        have[s[right]]++;
        while (satisfied()) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            have[s[left]]--;
            left++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}

Flaws & bottlenecks

  • Every "satisfied?" test scans all distinct letters of t, so cost is multiplied by that count.
  • Two maps are kept in sync and a closure allocates arrays on every call (spreading the map into entries).
  • Easy to get wrong: forgetting that have must be decremented when the left edge moves.

Interviewer cross-questions

Why is this O(n) pointer movement but not O(n) time?

Say: The window itself moves O(n) times, but each validity check loops over all distinct letters of t (up to 52 for letters, more for Unicode). Total time is O(n · distinct letters). The single missing counter removes that factor.

Why does shrinking from the left keep the answer correct?

Say: Once the window covers t, any smaller valid window ending at or before right must start at or after left. Moving left forward while the window stays valid explores exactly those, and then right resumes: every window is considered once.

What if t is longer than s?

Say: No window can ever be valid, so the answer is the empty string. An up-front length check returns immediately instead of scanning s.

3 · advanced

Sliding window with a "missing" counter

time O(|s| + |t|)space O(σ)

Keep one table of needs that can go negative and one integer "missing". Entering a needed letter decrements missing; leaving a letter that makes a count positive again increments it. The window is valid exactly when missing is 0.

string minWindow(string s, string t) {
    if (t.size() > s.size()) return "";
    unordered_map<char, int> need;
    for (char ch : t) need[ch]++;
    int missing = t.size();
    int bestStart = 0;
    int bestLen = INT_MAX;
    int left = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        if (need[c] > 0) missing--;
        need[c]--;
        while (missing == 0) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            char d = s[left];
            need[d]++;
            if (need[d] > 0) missing++;
            left++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}

Flaws & bottlenecks

  • Map lookups with a default (?? 0) on every step add hashing overhead to an otherwise O(1) update.
  • Negative counters are subtle: a negative value means surplus, and mixing it up with "not in t" is a classic bug.
  • The invariant (missing counts only the letters still lacking) is easy to break when editing either branch.

Interviewer cross-questions

How do negative counters help?

Say: need[c] > 0 means the window still lacks c; need[c] ≤ 0 means it has enough (a negative value is the surplus). So "was this letter actually required?" is just need[c] > 0 before decrementing, and the same sign test tells you on removal whether the window just lost a required letter.

Why is the total O(|s| + |t|) even though shrinking is a loop?

Say: left only moves forward and never passes right, so across the whole run it advances at most |s| times. Each loop iteration does O(1) work. Building the need table costs O(|t|).

How would you return all minimum windows?

Say: Instead of overwriting the best, keep a list: when the current length equals bestLen append the start index, and when it is smaller clear the list first. Overlapping windows are expected.

4 · expert

Flat counter array, bulk trim, early exit

time O(|s| + |t|)space O(1) (fixed 128-slot table)

Replace the map by a 128-slot Int32Array, trim surplus letters from the left in one tight loop as soon as the window is valid, and stop as soon as a window the size of t is found, since nothing shorter can exist.

string minWindow(const string& s, const string& t) {
    int n = s.size();
    int m = t.size();
    if (m == 0 || m > n) return "";
    int need[256] = {0}; // one slot per byte value
    for (int i = 0; i < m; i++) need[(unsigned char)t[i]]++;
    int missing = m;
    int bestStart = 0;
    int bestLen = n + 1;
    int left = 0;
    for (int right = 0; right < n; right++) {
        if (need[(unsigned char)s[right]]-- > 0) missing--;
        if (missing > 0) continue;
        while (need[(unsigned char)s[left]] < 0) need[(unsigned char)s[left++]]++;
        if (right - left + 1 < bestLen) {
            bestLen = right - left + 1;
            bestStart = left;
            if (bestLen == m) break;
        }
        need[(unsigned char)s[left++]]++;
        missing++;
    }
    return bestLen > n ? "" : s.substr(bestStart, bestLen);
}

Flaws & bottlenecks

  • ASCII only: characters with codes ≥ 128 index outside the table, so reads and writes are silently ignored in a typed array; Unicode needs a wider table or a map.
  • The post-increment tricks (need[...left++]++) are compact but hard to read and easy to get wrong.
  • The early exit only fires when the answer happens to have length |t|.

Interviewer cross-questions

Why is the flat array faster than a Map?

Say: One contiguous block indexed by character code: no hashing, no collision handling, no boxed entries, and the whole 512-byte table sits in L1 cache. Each update is a load and a store.

Why can you trim without re-checking validity?

Say: A slot below zero means the window holds more of that letter than t needs, so removing the leftmost copy cannot make the window invalid. You can therefore advance left in a tight loop until the leftmost letter is one the window actually needs (slot = 0).

How do you support Unicode?

Say: Use a Map keyed by code point (or grapheme cluster), or a table sized to the alphabet actually present, after normalizing both strings. Iterating by code point rather than UTF-16 unit avoids splitting surrogate pairs.

Synchronized code walkthrough

Showing: Every window, shortest lengths first — shares the player above; click any step to jump.

string minWindow(string s, string t) {
    auto covers = [&](const string& w) {
        int cnt[256] = {0};
        for (unsigned char c : t) cnt[c]++;
        for (unsigned char c : w) cnt[c]--;
        for (unsigned char c : t) if (cnt[c] > 0) return false;
        return true;
    };
    int n = s.size();
    for (int len = t.size(); len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            string window = s.substr(i, len);
            if (covers(window)) return window;
        }
    }
    return "";
}