Minimum Window Substring: variable window with a coverage counter

This is the one in the sliding-window series where the window size is completely unconstrained, both pointers can move at any rate relative to each other, and you still have to do it in a single pass. The mechanics of the two-pointer walk are straightforward by now — what makes problem 76 genuinely hard is the validity check. How do you know, in O(1), that the current window covers all the characters in t?

The answer is a counter that most writeups call have and need — or formed and required. This article is about why that counter exists and what it's actually doing.

The problem and what the constraints force

Given strings s and t, return the shortest substring of s that contains every character in t (including duplicates). If no such substring exists, return "".

s = "ADOBECODEBANC", t = "ABC" -> "BANC".

s = "a", t = "aa" -> "". Both as from t must be present; s only has one.

The duplicates clause is the thing that bites people. t = "AA" requires two As in the window, not one. A frequency map, not a set, is the right data structure.

Now read the constraints carefully: both s and t can be up to 10^5 characters, and s and t consist only of uppercase and lowercase English letters. Two things fall out of that:

• 10^5 kills any O(m²) approach. You need O(m + n). That means at most one pass over s — sliding window is the obvious candidate.
• "English letters only" means the alphabet is bounded at 52 characters. That lets you replace hash maps with fixed-size arrays (int[128]) for a constant-factor speedup, though it does not change asymptotic complexity.

Brute force: O(m² x n)

The naive read of the problem: iterate every possible starting index i, extend j to the right until the window s[i:j+1] covers all of t, record the length, move on.

The version below includes a break once the first valid window for a given i is found — there is no reason to keep extending, since we want the shortest. This gives O(m × n) per starting index in the best case (valid window found early) but stays O(m²×n) in the worst case when no valid window exists (no break ever fires) or when valid windows are always near the end.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
 
        need = Counter(t)
        min_len = float("inf")
        result = ""
 
        for i in range(len(s)):
            window = {}
            for j in range(i, len(s)):
                c = s[j]
                window[c] = window.get(c, 0) + 1
                if all(window.get(ch, 0) >= cnt for ch, cnt in need.items()):
                    if j - i + 1 < min_len:
                        min_len = j - i + 1
                        result = s[i : j + 1]
                    break  # shortest for this i — no need to extend further
 
        return result

public class Solution {
    public string MinWindow(string s, string t) {
        var need = new Dictionary<char, int>();
        foreach (char c in t) need[c] = need.GetValueOrDefault(c, 0) + 1;
 
        int minLen = int.MaxValue;
        string result = "";
 
        for (int i = 0; i < s.Length; i++) {
            var window = new Dictionary<char, int>();
            for (int j = i; j < s.Length; j++) {
                char c = s[j];
                window[c] = window.GetValueOrDefault(c, 0) + 1;
                bool valid = true;
                foreach (var kv in need)
                    if (window.GetValueOrDefault(kv.Key, 0) < kv.Value) { valid = false; break; }
                if (valid) {
                    if (j - i + 1 < minLen) { minLen = j - i + 1; result = s.Substring(i, j - i + 1); }
                    break;
                }
            }
        }
        return result;
    }
}

With m = n = 10^5 and no valid window, this hits O(m²×n) — completely unusable. The inner validity check scans the entire need map at each inner step. You need a way to know — without scanning anything — whether the current window is already valid.

The key insight: count satisfied characters, not all characters

Before sliding, build a frequency map of t:

need = {'A': 1, 'B': 1, 'C': 1}   (for t = "ABC")
required = 3                        (len(need) — number of distinct chars to satisfy)

Then maintain a second frequency map window_counts for characters inside the current window, and a single integer have that counts how many of the required distinct characters are currently satisfied.

A character c is "satisfied" when window_counts[c] >= need[c]. Crucially, have only changes at exact thresholds:

• Increment have when adding s[right] causes window_counts[c] to reach need[c] exactly (going from under-satisfied to satisfied).
• Decrement have when removing s[left] causes window_counts[c] to drop below need[c] (going from satisfied to under-satisfied).

When have == required, the window is valid. No map scan — a single integer comparison.

The state machine for the algorithm looks like this:

The sliding window solution

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
 
        from collections import Counter
        need = Counter(t)
        required = len(need)
 
        left = 0
        have = 0
        window_counts = {}
 
        best_len = float("inf")
        best_left = 0
 
        for right in range(len(s)):
            c = s[right]
            window_counts[c] = window_counts.get(c, 0) + 1
 
            # Did adding c push this character to fully satisfied?
            if c in need and window_counts[c] == need[c]:
                have += 1
 
            # Shrink from the left while the window is valid
            while have == required:
                # Record if this is the best window so far
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_left = left
 
                # Remove the leftmost character
                left_c = s[left]
                window_counts[left_c] -= 1
                if left_c in need and window_counts[left_c] < need[left_c]:
                    have -= 1
                left += 1
 
        return "" if best_len == float("inf") else s[best_left : best_left + best_len]

public class Solution {
    public string MinWindow(string s, string t) {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";
 
        var need = new Dictionary<char, int>();
        foreach (char c in t) need[c] = need.GetValueOrDefault(c, 0) + 1;
        int required = need.Count;
 
        var windowCounts = new Dictionary<char, int>();
        int left = 0, have = 0;
        int bestLen = int.MaxValue, bestLeft = 0;
 
        for (int right = 0; right < s.Length; right++) {
            char c = s[right];
            windowCounts[c] = windowCounts.GetValueOrDefault(c, 0) + 1;
 
            if (need.ContainsKey(c) && windowCounts[c] == need[c])
                have++;
 
            while (have == required) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestLeft = left;
                }
                char lc = s[left];
                windowCounts[lc]--;
                if (need.ContainsKey(lc) && windowCounts[lc] < need[lc])
                    have--;
                left++;
            }
        }
 
        return bestLen == int.MaxValue ? "" : s.Substring(bestLeft, bestLen);
    }
}

Walking through the example, step by step

s = "ADOBECODEBANC", t = "ABC".

Initial state: need = {A:1, B:1, C:1}, required = 3, have = 0, left = 0.

Phase 1 — expand right until valid:

Window s[0:6] = "ADOBEC", length 6. Record as best.

Phase 1 — shrink from left:

Remove A (left=0): window_counts[A] drops to 0, which is below need[A]=1 -> have=2. left=1. Not valid anymore, stop shrinking.

Phase 2 — expand right again:

Window is valid at left=1. Shrink:

• Remove D (left=1): not in need, left=2.
• Remove O (left=2): not in need, left=3.
• Remove B (left=3): window_counts[B] drops from 2 to 1, still >= need[B]=1, have stays at 3. left=4.
• Remove E (left=4): not in need, left=5.
• At left=5, before removing: window is s[5:11] = "CODEBA", length 6. No improvement.
• Remove C (left=5): window_counts[C] drops to 0 < need[C]=1 -> have=2. left=6.

Phase 3 — expand again:

Window valid at left=6. Shrink:

• Remove O (left=6): not in need, left=7.
• Remove D (left=7): not in need, left=8.
• Remove E (left=8): not in need, left=9.
• At left=9, before removing: window is s[9:13] = "BANC", length 4. New best. best_left=9, best_len=4.
• Remove B (left=9): window_counts[B] drops to 0 < need[B]=1 -> have=2. left=10.

right exhausted. Return s[9:13] = "BANC".

Why the coverage counter is the whole trick

Without have, you'd need to check whether all entries in need are satisfied every time you want to shrink. That's O(|need|) per step — O(26) for ASCII letters. It does not change the asymptotic complexity but adds a constant factor that compounds.

More importantly, the threshold check (window_counts[c] == need[c]) is the exact moment a character transitions from under-satisfied to satisfied. It fires at most once per character per window expansion. The counter converts a map-scan into a counter-comparison. Same information, O(1) per step.

The same idea appears whenever you need to know if a sliding window satisfies a frequency constraint. Permutation in String (567) uses an identical counter. Longest Substring Without Repeating Characters (3) does not need it — uniqueness is a different constraint — but the shrink-when-invalid loop is the same structure.

Complexity comparison

The space bound for the optimal solution is technically O(alphabet size) since both maps are bounded by the number of distinct characters — O(1) for ASCII letters. With arbitrary Unicode input it becomes O(m + n) in the worst case. For the constrained problem (English letters only), you can swap both hash maps for int[128] arrays and get a meaningful constant-factor improvement in practice.

I'd ship the sliding window. The brute force has pedagogical value but hits a wall immediately with 10^5 characters — you'd be waiting seconds on a single test case.

Edge cases and how the code handles them

s shorter than t. No window can contain all of t, so have never reaches required and the loop exits normally. The code returns "" because best_len stays at infinity. An explicit early return (if len(s) < len(t): return "") avoids the iteration entirely.

t has a character not in s. Same: have never reaches required. No special handling needed — the main loop simply runs through all of s without the inner while ever firing.

t has duplicate characters like "AA". The most common source of bugs here. need['A'] = 2, so have only increments when window_counts['A'] hits exactly 2. A window with one A leaves have unchanged. The frequency map handles this correctly as long as you compare counts, not just presence.

s == t. The first valid window found is the entire string. The code records it, then attempts to shrink — but shrinking always drops have immediately because every character in the window is needed exactly once. Returns s in its entirety.

s = "a", t = "a". right=0 adds A, have reaches 1 == required, records best_len=1, then shrinks: removing A drops have to 0, left=1. Loop exits. Returns "a". Correct.

Series placement: what this problem adds

In the sliding-window series, earlier problems have fixed or predictable window sizes. Longest Substring Without Repeating Characters (3) already introduced the shrink-when-invalid pattern, but its validity test is simple: is the incoming character already in the window? A set and one if suffice.

Problem 76 adds two complications at once: the window validity now depends on a frequency constraint (not just presence), and you are minimising the window size rather than maximising it. The coverage counter is the answer to the frequency part. The minimise-on-shrink pattern (record best, then shrink) is the answer to the direction part.

After this problem, the next natural step is problems where the valid window condition involves multiple independent constraints — for example, sliding windows over colored elements where you need a minimum count of each color. The have/need pattern scales directly to those.

Related problems

Permutation in String (567) — fixed-size window, same have/need counter. The window size is len(p), so you only move left when right - left + 1 > len(p). Simpler than 76 because you do not need to minimise; you stop as soon as have == required.

Find All Anagrams in a String (438) — same fixed-size window as 567, but instead of stopping at the first match you collect all starting indices where have == required. Same counter, different output shape.

Longest Substring Without Repeating Characters (3) — variable window, no frequency map needed. The validity constraint is "no character appears more than once", maintained with a set. Shrink when the incoming character already exists in the window.

Minimum Size Subarray Sum (209) — variable window over integers with a sum constraint instead of a frequency constraint. The shrink condition is different but the expand-then-shrink loop structure is identical.