Minimum Window Substring [Hard] — The Canonical Sliding Window Problem

Problem Statement

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

You may assume the answer is unique.

Example 1 — Standard case:

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" contains A, B, and C. No shorter window does.

Example 2 — Duplicate characters in t:

Input:  s = "AA", t = "AA"
Output: "AA"
Explanation: Both characters must appear. The full string is the only valid window.

Example 3 — Edge case, t not in s:

Input:  s = "A", t = "B"
Output: ""
Explanation: 'B' never appears in s, so no valid window exists.

Constraints:

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

• Why This Problem Matters
• The Core Sliding Window Framework
• The "Formed" Counter Technique
• The Full Algorithm — Every Variable Explained
• Visual Dry Run — s = "ADOBECODEBANC", t = "ABC"
• Common Mistakes
• Solutions
• Brute Force — O(n² · m)
• Optimal — O(n + m) Sliding Window with "Formed" Counter
• Complexity Analysis
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 76 is not just another hard problem — it is the hard sliding window problem. You will find it on the short list of must-know patterns at every tier-1 company. Google uses it to check whether you can navigate complex state management under a two-pointer loop. Meta asks it to see if you can reason about frequency maps without reaching for O(n²) nested loops. Amazon puts it in system-design adjacent rounds where they want candidates who think in terms of incremental updates rather than full recomputation.

Here is why it earns that reputation: the naive solution is obvious — try every substring of s, check if it contains all of t, track the shortest. That is O(n² · m) and will time out on the given constraints. The fast solution requires you to realize that you can maintain the answer incrementally as you expand and shrink a window. That leap — from "check the whole window each time" to "update a single counter each time" — is exactly the kind of algorithmic intuition interviewers are probing for.

The secondary reason is that the "formed" counter technique you learn here transfers directly to at least six other LeetCode problems. Once you internalize this pattern, problems like Permutation in String (LC 567), Longest Substring with At Most K Distinct Characters (LC 340), and Fruit Into Baskets (LC 904) all become recognizable variants.

The Core Sliding Window Framework

Every sliding window problem fits one of two templates:

1. Fixed-size window — window width is given (size k), slide it across.
2. Variable-size window — window must satisfy a condition; expand until valid, shrink to optimize.

This problem is type 2. The window s[l..r] is valid when it contains every character of t with at least the required frequency. Our goal is to find the shortest valid window.

The general loop looks like this:

l = 0
for r in 0..n-1:
    include s[r] in window
    while window is valid:
        update_result(l, r)
        exclude s[l] from window
        l += 1

The challenge is the phrase "window is valid." If you check by comparing the entire frequency map of the window against the frequency map of t on every iteration, you spend O(m) per step — giving you O(n · m) total, which is no better than brute force for large t. The key insight is the formed counter.

The "Formed" Counter Technique

Instead of asking "do all character counts match?" on every step, we ask a much cheaper question: "how many distinct characters in t have reached their required count in the current window?" We store this as a single integer called formed (or have).

The rules are simple:

• When we add character c to the window: if window[c] just reached need[c] (meaning it became equal, not just exceeded), increment formed.
• When we remove character c from the window: if window[c] just dropped below need[c], decrement formed.
• The window is valid when formed == need_count, where need_count = len(set of distinct characters in t).

The critical word in both rules is "just." We only change formed at the exact threshold — when a count crosses the boundary, not every time a count changes. This is what makes each pointer movement O(1).

Why does equality checking with unique characters work, rather than checking all characters? Because t = "AABC" contributes need_count = 3 (three distinct chars: A, B, C). Once window['A'] >= 2, window['B'] >= 1, and window['C'] >= 1, the window is valid regardless of what else it contains. We need only track per-distinct-character satisfaction, not total character counts. This saves us from iterating over the map on every step.

This technique reduces the validity check from O(|unique chars in t|) to O(1) per pointer movement.

The Full Algorithm — Every Variable Explained

need        = frequency map of t          (how many of each char we require)
need_count  = number of distinct chars in t
window      = frequency map of current window (starts empty)
formed      = number of distinct chars in t currently satisfied in window
l           = left pointer (start of window)
result      = (result_length, result_left, result_right)

Algorithm:

1. Build need by counting every character in t. Set need_count = len(need).
2. Initialize window = {}, formed = 0, l = 0, result = (infinity, 0, 0).
3. Iterate r from 0 to len(s) - 1:
   • Add s[r] to window.
   • If s[r] is in need and window[s[r]] == need[s[r]], increment formed.
   • While formed == need_count (window is valid):
     • If r - l + 1 < result[0], update result = (r - l + 1, l, r).
     • Remove s[l] from window (decrement count).
     • If s[l] is in need and window[s[l]] < need[s[l]], decrement formed.
     • Increment l.
4. Return s[result[1] : result[2] + 1] if result[0] != infinity, else "".

The inner while loop looks expensive, but each character is added to the window at most once (when r visits it) and removed at most once (when l passes it). Total work across all iterations is O(n + m).

Visual Dry Run — s = "ADOBECODEBANC", t = "ABC"

First, build need = {A:1, B:1, C:1}, need_count = 3.

formed == 3. Window is valid: s[0..5] = "ADOBEC", length 6. Record result (6, 0, 5).

Now shrink: remove s[0] = 'A'. window[A] drops to 0, which is below need[A]=1. formed-- → 2. l = 1.

Window is no longer valid. Continue expanding r.

formed == 3. Window is valid: s[1..10] = "DOBECODEBA", length 10. Longer than 6 — don't update result.

Shrink from left: remove s[1] = 'D'. D not in need. l = 2. Still valid. Remove s[2] = 'O'. O not in need. l = 3. Still valid. Remove s[3] = 'B'. window[B] drops to 1 (was 2). Still >= need[B]=1. formed stays 3. l = 4. Still valid.

Current window s[4..10] = "ECODEBA", length 7. Longer than 6 — no update.

Remove s[4] = 'E'. E not in need. l = 5. Window s[5..10] = "CODEBA", length 6. Ties current best. Since we only update on strictly smaller, no update.

Remove s[5] = 'C'. window[C] drops to 0 < need[C]=1. formed-- → 2. l = 6. Not valid.

Continue expanding r.

formed == 3. Window valid: s[6..12] = "ODEBANC", length 7. Longer than 6.

Shrink: remove s[6] = 'O'. Not in need. l = 7. Window s[7..12] = "DEBANC", length 6. Not smaller. Remove s[7] = 'D'. Not in need. l = 8. Window s[8..12] = "EBANC", length 5. New minimum! Record (5, 8, 12). Remove s[8] = 'E'. Not in need. l = 9. Window s[9..12] = "BANC", length 4. New minimum! Record (4, 9, 12). Remove s[9] = 'B'. window[B] drops to 0 < need[B]=1. formed-- → 2. l = 10. Not valid.

r has reached the end. Return s[9:13] = "BANC". Correct.

Common Mistakes

Mistake 1: Incrementing formed every time a needed character is added (not just at threshold)

Wrong approach: if c in need: formed += 1. This overcounts. If you need 2 A's and you add a third, you should not increment formed again — it was already satisfied. The correct check is window[c] == need[c] (exact equality on the way up).

Mistake 2: Forgetting to check c in need before touching formed

Characters not in t are tracked in window for correctness, but they must never affect formed. If s contains a 'Z' and t has no 'Z', updating formed based on 'Z' will make the window appear valid before it actually is.

Mistake 3: Updating the result after shrinking instead of before

The valid window exists at the moment formed == need_count. The result must be recorded at the top of the while loop, before the left pointer moves. Recording it after the shrink means you miss the actual minimum window.

Mistake 4: Off-by-one when reconstructing the result string

Storing (left, right) as inclusive indices means the return value is s[left : right + 1] in Python and s.slice(left, right + 1) in JavaScript. Forgetting the +1 returns a string one character short.

Mistake 5: Not handling the "t not in s" case

If formed never reaches need_count (e.g., t = "B", s = "AAA"), the result remains (infinity, 0, 0). Return "" in this case. Omitting this check causes an index-out-of-bounds or returns garbage.

Solutions

Brute Force — O(n² · m)

Enumerate every substring of s and check if it contains all characters of t. Simple to write, guaranteed TLE on large inputs, but useful for verifying your optimal solution on small cases.

Python:

def minWindow_brute(s: str, t: str) -> str:
    from collections import Counter
    need = Counter(t)
    best = ""
    n = len(s)

    for left in range(n):
        window = {}
        for right in range(left, n):
            c = s[right]
            window[c] = window.get(c, 0) + 1

            # Check if window satisfies all requirements
            valid = all(window.get(ch, 0) >= cnt for ch, cnt in need.items())
            if valid:
                if not best or (right - left + 1) < len(best):
                    best = s[left:right + 1]
                break  # any further right expansion only makes it longer

    return best

JavaScript:

function minWindowBrute(s, t) {
    const need = {};
    for (const c of t) need[c] = (need[c] || 0) + 1;

    let best = "";
    const n = s.length;

    for (let left = 0; left < n; left++) {
        const window = {};
        for (let right = left; right < n; right++) {
            const c = s[right];
            window[c] = (window[c] || 0) + 1;

            // Check if all required chars are satisfied
            const valid = Object.entries(need).every(
                ([ch, cnt]) => (window[ch] || 0) >= cnt
            );
            if (valid) {
                if (!best || right - left + 1 < best.length) {
                    best = s.slice(left, right + 1);
                }
                break; // expanding right only grows the window
            }
        }
    }
    return best;
}

Optimal — O(n + m) Sliding Window with "Formed" Counter

Python:

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    # Step 1: Build frequency map of t
    need = {}
    for c in t:
        need[c] = need.get(c, 0) + 1

    need_count = len(need)   # number of DISTINCT chars required
    window = {}              # frequency map of current window
    formed = 0               # distinct chars in t currently satisfied

    l = 0
    result_len = float("inf")
    result_l, result_r = 0, 0

    for r in range(len(s)):
        c = s[r]
        # Expand: add s[r] to window
        window[c] = window.get(c, 0) + 1

        # Only update formed when the exact threshold is crossed (not exceeded)
        if c in need and window[c] == need[c]:
            formed += 1

        # Shrink: while window is valid, try to minimize it
        while formed == need_count:
            # Record result before shrinking
            if r - l + 1 < result_len:
                result_len = r - l + 1
                result_l, result_r = l, r

            # Remove leftmost character from window
            left_char = s[l]
            window[left_char] -= 1

            # Update formed if this char drops below required count
            if left_char in need and window[left_char] < need[left_char]:
                formed -= 1

            l += 1

    if result_len == float("inf"):
        return ""  # t characters not present in s
    return s[result_l : result_r + 1]

JavaScript:

function minWindow(s, t) {
    if (!t || !s) return "";

    // Step 1: Build frequency map of t
    const need = {};
    for (const c of t) {
        need[c] = (need[c] || 0) + 1;
    }

    const needCount = Object.keys(need).length; // distinct chars needed
    const window = {};                           // current window frequencies
    let formed = 0;                              // satisfied distinct chars

    let l = 0;
    let resultLen = Infinity;
    let resultL = 0, resultR = 0;

    for (let r = 0; r < s.length; r++) {
        const c = s[r];
        // Expand: include s[r] in window
        window[c] = (window[c] || 0) + 1;

        // Increment formed only when the count exactly reaches the requirement
        if (need[c] !== undefined && window[c] === need[c]) {
            formed++;
        }

        // Shrink: while valid, try to minimize
        while (formed === needCount) {
            // Record smallest valid window before shrinking
            if (r - l + 1 < resultLen) {
                resultLen = r - l + 1;
                resultL = l;
                resultR = r;
            }

            // Remove leftmost character
            const leftChar = s[l];
            window[leftChar]--;

            // If this char now falls below its required count, window is invalid
            if (need[leftChar] !== undefined && window[leftChar] < need[leftChar]) {
                formed--;
            }

            l++;
        }
    }

    return resultLen === Infinity ? "" : s.slice(resultL, resultR + 1);
}

Complexity Analysis

Where n = len(s) and m = len(t).

Time — O(n + m):

• Building need costs O(m).
• The right pointer r visits each character of s exactly once: O(n).
• The left pointer l also visits each character at most once across all shrink steps: O(n).
• Each pointer movement does O(1) work (hash map lookup and update, formed check).
• Total: O(n + m).

Space — O(m):

• need stores at most |unique chars in t| entries, bounded by min(m, 52) for English letters.
• window stores at most |unique chars in s| entries, bounded by 52 for English letters.
• In practice both maps are O(1) since there are only 52 possible characters, but we write O(m) to be general.

Follow-up Questions

What if t contains wildcard characters? Standard frequency maps break down. You would need to adapt the validity check to handle pattern matching, likely requiring a different approach such as regex or trie-based matching.

LC 567 — Permutation in String (Medium) Find whether any permutation of t exists as a substring in s. This is the fixed-size window variant of the same pattern: the window size is fixed at len(t), and the formed counter tells you when the window is a permutation. Nearly identical code, just remove the shrink loop and replace it with a fixed-size slide.

LC 727 — Minimum Window Subsequence (Hard, Premium) Find the shortest substring of s1 such that t (called s2) is a subsequence of it — meaning the characters of t must appear in order, though not necessarily contiguously. The frequency-map approach does not work here because order matters. The standard solution uses two-pointer backtracking: scan forward to find the end of a valid subsequence, then scan backward to find the tightest left boundary, then advance and repeat.

LC 30 — Substring with Concatenation of All Words (Hard) Find all starting indices of substrings in s that are a concatenation of all words in a given list. Words have fixed length, so you slide a window of size total_words * word_length and use a frequency map of words instead of characters.

This Pattern Solves

The "expand to satisfy, shrink to optimize, use a counter to track satisfaction in O(1)" pattern appears across a whole family of problems:

• Longest Substring with At Most K Distinct Characters (LC 340) — formed is replaced by a count of distinct chars in the window.
• Fruit Into Baskets (LC 904) — same as LC 340 with k=2.
• Longest Repeating Character Replacement (LC 424) — tracks most frequent char count instead of satisfaction.
• Minimum Size Subarray Sum (LC 209) — numeric sum instead of character frequency.

Any time you see "find the shortest/longest subarray/substring satisfying condition X," consider whether X can be maintained with an O(1) counter update on each pointer move. If yes, you have an O(n) sliding window solution.

Key Takeaway

The formed counter is the algorithmic core of this problem: instead of revalidating the entire frequency map on every step (O(|t|) per step), you maintain a single integer that crosses a threshold exactly when a character's count is satisfied or violated. This reduces window validity checks to O(1) and makes the whole algorithm O(n + m). Once you see this trick, every "valid window" sliding window problem becomes a straightforward variant — which is exactly why this problem sits at the top of every serious interview prep list.