Minimum Window Substring

Problem Statement

Given two strings s and t, 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 "".

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: s has only one 'a'; cannot cover two.

Constraints:

1 <= s.length, t.length <= 10^5.
s and t consist of English letters.

Difficulty: Hard (common enough to be treated as a Medium-hard in practice) LC: 76 Round: Technical R1

Pattern Recognition

What is the input structure? Two strings — s (haystack) and t (needle frequency profile).
What are we optimizing? Minimum length substring of s that contains all character counts of t.
What pattern does this fit? Variable-size sliding window with a frequency map.
Why does this pattern fit? Expand right until the window covers t; then shrink left while the window still covers. The answer is the minimum length seen in any "covering" state.

Approach

Brute Force — Check Every Window

For each (l, r), check whether s[l..r] covers t.

Time: O(n^3) naive, O(n^2) with incremental count update. Space: O(charset). Why insufficient: TLE for n = 10^5.

Optimal — Sliding Window with Formed/Required Counter

Key Insight: Track how many distinct characters in the window have met their required count. The window is valid when formed == required. Expand while invalid; shrink while valid.

Step-by-step:

Build need = character frequency map of t. Let required = need.size().
Initialize have = {}, formed = 0, left = 0, bestLen = Infinity.
For right from 0 to n-1:
- Let c = s[right]. Increment have[c].
- If c is in need and have[c] == need[c] exactly, increment formed.
- While formed == required:
  - Record if this is the smallest window.
  - Let lc = s[left]. Decrement have[lc].
  - If lc is in need and have[lc] < need[lc], decrement formed.
  - left++.
Return the best window, or "" if none.

Time: O(n + m). Space: O(charset).

Walkthrough

Trace on s = "ADOBECODEBANC", t = "ABC":

need = {A:1, B:1, C:1}, required = 3.

Expanding right:

right	c	formed	window valid?	shrink action
0	A	1	no
1	D	1	no
2	O	1	no
3	B	2	no
4	E	2	no
5	C	3	yes	try to shrink

At right=5, window is "ADOBEC" (len 6). Shrink:

Remove A at left=0 → formed drops to 2 (A count below required). Break shrink.

Continue expanding:

right	c	action	best
6	O	have[O]=2	6
7	D	have[D]=2	6
8	E	have[E]=2	6
9	B	have[B]=2	6
10	A	have[A]=1, formed=3 → shrink

At right=10, window starts at left=1: "DOBECODEBA" (len 10). Shrink:

left=1, D: have[D]=1, D not in need. left=2.
left=2, O: have[O]=1, O not in need. left=3.
left=3, B: have[B]=1, still >= need[B]. left=4.
left=4, E: have[E]=1, E not in need. left=5.
left=5, C: have[C]=0 < need[C]=1, formed=2. left=6. Break.

Window at right=10, left=5 was "CODEBA" (len 6). Same as before.

Continue:

right	c	...	best window	best len
11	N	not relevant		6
12	C	have[C]=1, formed=3 → shrink

At right=12, left=6: window "ODEBANC" (len 7). Shrink:

left=6, O: left=7.
left=7, D: left=8.
left=8, E: left=9.
left=9, B: have[B]=0 < 1, formed=2, break. left=10.

Window at right=12, left=9 was "BANC" (len 4) — new best.

Answer: "BANC".

Implementation

TypeScriptC++

typescript

function minWindow(s: string, t: string): string {
    if (s.length < t.length) return "";

    const need = new Map<string, number>();
    for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);

    const required = need.size;
    let formed = 0;
    const have = new Map<string, number>();

    let bestLen = Infinity;
    let bestL = 0;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        have.set(c, (have.get(c) ?? 0) + 1);

        // Entering meets the need exactly — count this character as formed.
        if (need.has(c) && have.get(c) === need.get(c)) formed++;

        while (formed === required) {
            // Record candidate.
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestL = left;
            }
            // Slide left forward.
            const lc = s[left];
            have.set(lc, have.get(lc)! - 1);
            if (need.has(lc) && have.get(lc)! < need.get(lc)!) formed--;
            left++;
        }
    }
    return bestLen === Infinity ? "" : s.substring(bestL, bestL + bestLen);
}

cpp

#include <string>
#include <unordered_map>
#include <climits>

std::string minWindow(std::string s, std::string t) {
    if (s.size() < t.size()) return "";
    std::unordered_map<char, int> need, have;
    for (char c : t) need[c]++;

    int required = need.size(), formed = 0;
    int bestLen = INT_MAX, bestL = 0;
    int left = 0;

    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        have[c]++;
        if (need.count(c) && have[c] == need[c]) formed++;

        while (formed == required) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestL = left;
            }
            char lc = s[left];
            have[lc]--;
            if (need.count(lc) && have[lc] < need[lc]) formed--;
            left++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}

Watch out:

Duplicate characters in t. Need is a frequency map, not a set. t = "AABC" requires two A's.
formed increments only on exact equality. If have[c] > need[c], you already counted it; don't increment again.
Shrink condition. have[lc] < need[lc] (strict) on decrement, to decrement formed exactly when you lose the "exact match" state.

Complexity Analysis

	Time	Space
Brute Force	O(n^2) with incremental, O(n^3) naive	O(charset)
Optimal (Sliding Window)	O(n + m)	O(charset)

Bottleneck: Each character enters and leaves the window at most once — O(n + m) total work.

Edge Cases

t longer than s — impossible; return "".
t empty — undefined; return "" or throw.
t == s — return s.
All of s is one character — check if t is the same character repeated.
Multiple valid minimum windows — return any (LC specifies the first one found, which your left-first scan produces naturally).

LC 3 — Longest Substring Without Repeating Characters — Variable window, different admissibility.
LC 438 — Find All Anagrams in a String — Fixed window, exact-match admissibility.
LC 567 — Permutation in String — Same as 438 with a boolean return.
LC 30 — Substring with Concatenation of All Words — Hardest cousin; window of fixed structure over word boundaries.

Interview Strategy Notes

This is the canonical "hard sliding window" question. Expect 25-35 minutes in a Salesforce Technical R1. The formed counter trick is the key insight — many candidates try to track "does every char meet or exceed need?" directly on every shrink, which is O(charset) per shrink and hits TLE on large inputs. Practice writing the have[c] == need[c] increment and have[lc] < need[lc] decrement without thinking.

What is Expected at Each Level

Junior: Understands the sliding window shape but struggles with the admissibility tracking. Needs heavy hints on formed / required.

Mid-level: Writes the solution with some back-and-forth. Handles duplicates in t correctly. Explains complexity.

Senior: Implements cleanly on the first pass. Discusses the two-pointer invariant (left monotonic), handles Unicode considerations, and mentions the fixed-window variant (LC 438) as a simpler cousin.

Minimum Window Substring ​

Problem Statement ​

Pattern Recognition ​

Approach ​

Brute Force — Check Every Window ​

Optimal — Sliding Window with Formed/Required Counter ​

Walkthrough ​

Implementation ​

Complexity Analysis ​

Edge Cases ​

Related Problems ​

Interview Strategy Notes ​

What is Expected at Each Level ​