Minimum Window Substring — have/need Frequency Counter [LC 76, Google, Amazon, Facebook]

Problem Statement#

LeetCode 76 — Minimum Window Substring · Difficulty: Hard

Given two strings s and t of lengths m and n, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Constraints:

• m == s.length, n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters

Example 1:

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the smallest window containing A, B, and C.

Example 2:

Input:  s = "a", t = "a"
Output: "a"

Example 3:

Input:  s = "a", t = "aa"
Output: ""
Explanation: "a" contains only one 'a', but "aa" requires two.

Why This Problem Matters#

LC 76 is one of the most important hard problems in FAANG interviews. Google, Amazon, Facebook, and Microsoft all ask it because it requires combining several ideas simultaneously: frequency counting, a two-pointer shrinkable window, and the have/need counter that tracks when the window is valid in O(1) per step.

The key insight that elevates this from O(n²) to O(n+m) is the have counter: instead of recomputing whether all characters of t are covered on every window change, you maintain a single integer that increments only when a character's count in the window exactly meets the requirement, and decrements only when it drops below.

This is the template for all "minimum window covering a required set" problems. Once you master LC 76, problems like LC 567 (Permutation in String), LC 438 (Find All Anagrams), and LC 30 (Substring with Concatenation of All Words) become straightforward.

The Core Insight#

Step 1 — Build need. Count the frequency of each character in t. need is a frequency map: need[c] = how many times c must appear in the window.

Step 2 — have and needed. needed = number of distinct character types in t (i.e., len(need)). have = number of character types whose window count currently meets or exceeds the required count.

Step 3 — Expand right. For each new character s[right]:

• Increment window[s[right]].
• If window[s[right]] == need[s[right]], increment have (this type is now satisfied).

Step 4 — Shrink left (when valid). While have == needed (all types satisfied):

• Update the minimum window if the current one is smaller.
• Decrement window[s[left]].
• If window[s[left]] < need[s[left]], decrement have (this type is no longer satisfied).
• Advance left.

Key invariant: have == needed means the current window covers all of t.

Visual Dry Run#

Input: s = "ADOBECODEBANC", t = "ABC"

need = {A:1, B:1, C:1}, needed = 3

Final answer: "BANC"

Common Mistakes#

1. Incrementing have when window[c] >= need[c] instead of exactly ==. The have counter should increment only when the count first reaches the required level, not every time it increases beyond it. Using >= causes have to exceed needed and the window validity check breaks.

2. Decrementing have when window[c] < need[c] after removing from left. Only decrement have when the count drops below the required level (from need[c] to need[c]-1). If window[c] was already above need[c], removing one doesn't break the constraint.

3. Not checking if s[left] is in need before decrementing have. If s[left] is not in need, removing it from the window cannot invalidate any requirement. Always check if c in need before modifying have.

4. Using need.size instead of need.size() in JavaScript. Map.size is a property, not a method — use need.size (not need.size()). Calling it as a method returns undefined, breaking the loop termination.

5. Returning the wrong slice. The answer is s[start : start + min_len], not s[start : start + min_len - 1]. Track the start index and the length; compute the slice at the end with both values.

6. Not handling the case where t contains a character not in s. The algorithm handles this correctly — have never reaches needed because the required character is never seen in the window. The function returns "" as required.

Solutions#

Python#

from collections import Counter, defaultdict
 
def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""
 
    need = Counter(t)            # required frequency of each character in t
    needed = len(need)           # number of distinct character types required
 
    window = defaultdict(int)    # frequency of characters in the current window
    have = 0                     # number of character types currently satisfied
    left = 0                     # left boundary of window
    min_len = float('inf')       # length of smallest valid window found
    start = 0                    # start index of smallest valid window
 
    for right, c in enumerate(s):
        window[c] += 1           # expand window: include s[right]
 
        # Check if this character type is now satisfied
        if c in need and window[c] == need[c]:
            have += 1            # exactly met — increment have
 
        # Shrink from left while window is valid (all types satisfied)
        while have == needed:
            # Update minimum window if current is smaller
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left
 
            # Remove leftmost character from window
            outgoing = s[left]
            window[outgoing] -= 1
            # If this drops below the required count, window is no longer valid
            if outgoing in need and window[outgoing] < need[outgoing]:
                have -= 1
            left += 1            # advance left pointer
 
    return "" if min_len == float('inf') else s[start : start + min_len]

JavaScript#

function minWindow(s, t) {
    if (!s || !t) return "";
 
    const need = new Map();
    for (const c of t) {
        need.set(c, (need.get(c) || 0) + 1);  // build required frequency map
    }
    const needed = need.size;                   // distinct character types required
 
    const window = new Map();
    let have = 0;                               // character types currently satisfied
    let left = 0;
    let minLen = Infinity;
    let start = 0;
 
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        window.set(c, (window.get(c) || 0) + 1);  // expand window
 
        // Check if this character type is now exactly satisfied
        if (need.has(c) && window.get(c) === need.get(c)) {
            have++;
        }
 
        // Shrink from left while window is valid
        while (have === needed) {
            // Record this window if it is the smallest so far
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
 
            // Remove leftmost character
            const outgoing = s[left];
            window.set(outgoing, window.get(outgoing) - 1);
            // If this drops below the required count, window becomes invalid
            if (need.has(outgoing) && window.get(outgoing) < need.get(outgoing)) {
                have--;
            }
            left++;
        }
    }
 
    return minLen === Infinity ? "" : s.slice(start, start + minLen);
}

Complexity Analysis#

Each character in s is added to the window once (right pointer) and removed at most once (left pointer). The total work is O(m) for the main loop plus O(n) to build the need map. Space is O(m + n): O(n) for need and O(m) for window in the worst case.

Follow-up Questions#

1. LC 567 — Permutation in String: Fixed-size window version — check if any window of length |t| is an anagram of t. Same have/need logic, but left advances automatically when right - left + 1 > |t|.

2. LC 438 — Find All Anagrams in a String: Return all starting indices of windows that are anagrams. Same fixed-size window, collect start positions instead of minimum.

3. LC 30 — Substring with Concatenation of All Words: All words are the same length — slide a window in steps of word length, using word-frequency maps instead of character-frequency maps.

4. What if t is very large (n >> m)? A valid window must contain all characters of t, so it has length at least n. If n > m, no valid window exists — return "" immediately.

This Pattern Solves#

• LC 76 — Minimum Window Substring (this problem)
• LC 567 — Permutation in String (fixed-size window, anagram check)
• LC 438 — Find All Anagrams in a String (fixed-size window, collect starts)
• LC 3 — Longest Substring Without Repeating Characters (maximize window, one-type constraint)
• LC 159 — Longest Substring with At Most Two Distinct Characters (k-type constraint)

Key Takeaways#

• LC 76 is asked at Google, Amazon, Facebook, and Microsoft — it is the hardest canonical sliding-window problem and appears at both phone screen and onsite rounds.
• Build need as a frequency map of t; define needed = len(need) (distinct types) and have (types whose window count meets the requirement).
• Only increment have when window[c] == need[c] exactly (first time this type is satisfied); only decrement when window[c] drops below need[c].
• Shrink from the left whenever have == needed — record the window if it is the smallest, then remove the leftmost character and advance left.
• Both left and right move forward at most m times; the total work is O(m + n).
• Track start (not just min_len) when updating the minimum window; return s[start : start + min_len] at the end.
• This have/need counter eliminates O(n) revalidation on every window change — the central optimization that makes the algorithm O(m) instead of O(m·n).