76. Minimum Window Substring

Given strings s and t, find the shortest contiguous substring of s that contains every character of t (with multiplicity). A two-pointer sliding window with a need / have counter finds it in O(|s| + |t|) time.

● HardSliding WindowHash MapTypeScript

PROBLEM What we're solving

Given s = "ADOBECODEBANC" and t = "ABC", return the shortest window in s that contains 'A', 'B', and 'C'. Answer: "BANC". If no such window exists, return "". Characters in t may repeat (e.g. t="AA" requires two As in the window).

KEY IDEA Expand right until valid; contract left to minimize

Insight → maintain a window [L..R] and two maps: what we need (from t) and what the current window has. A single integer have counts how many distinct characters have hit their required frequency. When have === required the window is valid — record it, then advance L to shrink it. You only ever need one pass over s.

RECIPE Expand → record → contract → repeat

0 · Build the need map. Count each character of t; store required = need.size (distinct chars needed).
1 · Expand R. Add s[R] to the window map. If its count just reached the required amount, increment have.
2 · Contract while have === required. Record the window if it's the smallest so far, then remove s[L] from the window map. If that drops the count below its requirement, decrement have. Advance L.
3 · Return. Slice s at the saved best indices, or "" if no valid window was ever found.

Classic confusion → people increment have on every match instead of only when the window count exactly reaches the required count. If t = "AA"you need two A's; adding a third A to the window must not increment have again — window.get(c) === need.get(c) handles this precisely.

COST Complexity & trade-offs

Brute force (all substrings)

O(|s|²·|t|)

Check every substring; each check is O(|t|).

Sliding window + hash map

O(|s| + |t|)

Each pointer advances at most |s| times; setup is O(|t|).

Space is O(|Σ|)— at most the size of the character alphabet for the two maps. In the worst case (all distinct chars) that's O(|s| + |t|) but bounded by the alphabet.

Pattern transfer → the same have / required counter trick applies to Permutation in String (fixed-size window), Find All Anagrams in a String, and Longest Substring Without Repeating Characters. Any time you see "shortest / longest window containing some set of elements," reach for this template.

RUN IT Expand right, contract left, record the best

s =t =

step 0 / 34

STARTBuild need map from t="ABC": A:1, B:1, C:1. need 3 distinct chars. Start L=R=0.

1function minWindow(s: string, t: string): string {
2  if (t.length === 0) return '';
3 
4  // Build the "need" map: how many of each t-char we require
5▶  const need = new Map<string, number>();
6▶  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
7▶  const required = need.size; // distinct chars we must satisfy
8 
9▶  const window = new Map<string, number>(); // current window counts
10▶  let have = 0;   // distinct chars currently satisfied
11▶  let L = 0;
12 
13▶  let bestLen = Infinity;
14▶  let bestL = 0, bestR = 0;
15 
16  for (let R = 0; R < s.length; R++) {
17    // 1. Expand: add s[R] to the window
18    const c = s[R];
19    window.set(c, (window.get(c) ?? 0) + 1);
20    if (need.has(c) && window.get(c) === need.get(c)) {
21      have++; // this char's count just hit its requirement
22    }
23 
24    // 2. Contract: shrink from the left while window is valid
25    while (have === required) {
26      const len = R - L + 1;
27      if (len < bestLen) { bestLen = len; bestL = L; bestR = R; }
28 
29      const lc = s[L];
30      window.set(lc, window.get(lc)! - 1);
31      if (need.has(lc) && window.get(lc)! < need.get(lc)!) {
32        have--; // we dropped below requirement; window invalid
33      }
34      L++;
35    }
36  }
37 
38  return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);
39}

A0D1O2B3E4C5O6D7E8B9A10N11C12

State

—

have

required

—

best

∞

bestLen

—

bestL

—

bestR

{}

window

{ A:1, B:1, C:1 }

need

window [L..R]current R (just added)best window (final)

slowfast

TYPESCRIPT The solution, annotated

minWindow.ts
function minWindow(s: string, t: string): string {
  if (t.length === 0) return '';

  // Build the "need" map: how many of each t-char we require
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  const required = need.size; // distinct chars we must satisfy

  const window = new Map<string, number>(); // current window counts
  let have = 0;   // distinct chars currently satisfied
  let L = 0;

  let bestLen = Infinity;
  let bestL = 0, bestR = 0;

  for (let R = 0; R < s.length; R++) {
    // 1. Expand: add s[R] to the window
    const c = s[R];
    window.set(c, (window.get(c) ?? 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) {
      have++; // this char's count just hit its requirement
    }

    // 2. Contract: shrink from the left while window is valid
    while (have === required) {
      const len = R - L + 1;
      if (len < bestLen) { bestLen = len; bestL = L; bestR = R; }

      const lc = s[L];
      window.set(lc, window.get(lc)! - 1);
      if (need.has(lc) && window.get(lc)! < need.get(lc)!) {
        have--; // we dropped below requirement; window invalid
      }
      L++;
    }
  }

  return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);
}

Reading it block by block

Lines 4–7 — build the need map. One pass over t tallies how many of each character we require. required = need.size is the number of distinct characters we must satisfy — not t.length.

Lines 9–11 — initialize pointers and trackers. window mirrors the need map but for the current window. have counts how many distinct chars are currently satisfied. Both pointers start at 0; bestLen = Infinity so any valid window beats it.

Lines 13–20 — expand right. For each R, add s[R] to the window. Crucially, only increment have when the window count exactly equalsthe required count — extra copies don't count again.

Lines 22–31 — contract left. The inner while loop runs as long as the window is valid. Record the current window size; then remove s[L], decrement have if needed, and advance L. This greedily produces the smallest valid window before the window becomes invalid again.

Line 34 — return. If bestLen is still Infinity no window was ever valid → return "". Otherwise slice the saved indices. Note bestR + 1 is exclusive in slice.

Complexity → O(|s| + |t|) time — each of the two pointers travels at most |s| steps, and building the need map is O(|t|). O(|Σ|) space for the two maps (bounded by alphabet size).

INTERVIEWFollow-ups they'll ask

"What if t has duplicates, like t="AA"?" The need map stores the count (2), and have only increments when window.get(c) === need.get(c). No special case needed.
"Can s contain characters not in t?"Yes — they're added to the window map but never contribute to have since need.has(c) is false.
"How would you handle a follow-up asking for all minimum windows?" Collect every window whose length equals bestLen during the record step, instead of only keeping the first one.
"What if |s| is huge and |t| is small?" An optimization is to pre-filter s to only the characters that appear in t, reducing the effective length of s to at most |t| × k.
"Related problems?" Permutation in String (LC 567) uses the same trick with a fixed window size; Find All Anagrams (LC 438) collects every valid window; both are easier warm-ups for this pattern.

OPTIMAL Sliding Window

minWindow.ts
function minWindow(s: string, t: string): string {
  if (t.length === 0) return '';

  // Build the "need" map: how many of each t-char we require
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  const required = need.size; // distinct chars we must satisfy

  const window = new Map<string, number>(); // current window counts
  let have = 0;   // distinct chars currently satisfied
  let L = 0;

  let bestLen = Infinity;
  let bestL = 0, bestR = 0;

  for (let R = 0; R < s.length; R++) {
    // 1. Expand: add s[R] to the window
    const c = s[R];
    window.set(c, (window.get(c) ?? 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) {
      have++; // this char's count just hit its requirement
    }

    // 2. Contract: shrink from the left while window is valid
    while (have === required) {
      const len = R - L + 1;
      if (len < bestLen) { bestLen = len; bestL = L; bestR = R; }

      const lc = s[L];
      window.set(lc, window.get(lc)! - 1);
      if (need.has(lc) && window.get(lc)! < need.get(lc)!) {
        have--; // we dropped below requirement; window invalid
      }
      L++;
    }
  }

  return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);
}

Complexity → O(|s| + |t|) time — each of the two pointers travels at most |s| steps, and building the need map is O(|t|). O(|Σ|) space for the two maps (bounded by alphabet size).

ALT 1 Filtered-index sliding window

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

Pre-collect only the positions in s whose character is in t, then slide over that shorter list — a big win when s is huge but t is tiny.

approach-2.ts
function minWindow(s: string, t: string): string {
  if (t.length === 0 || 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;

  // Keep only the indices of s whose char appears in t.
  // Each entry is [indexInS, char]; this list can be far shorter than s.
  const filtered: Array<[number, string]> = [];
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (need.has(c)) filtered.push([i, c]);
  }

  const window = new Map<string, number>();
  let have = 0;
  let bestLen = Infinity;
  let bestL = 0, bestR = 0;

  // L and R now index into 'filtered', not into s directly.
  let L = 0;
  for (let R = 0; R < filtered.length; R++) {
    const c = filtered[R][1];
    window.set(c, (window.get(c) ?? 0) + 1);
    if (window.get(c) === need.get(c)) have++;

    // Contract while every requirement is met.
    while (have === required) {
      const start = filtered[L][0];
      const end = filtered[R][0];
      if (end - start + 1 < bestLen) {
        bestLen = end - start + 1;
        bestL = start;
        bestR = end;
      }

      const lc = filtered[L][1];
      window.set(lc, window.get(lc)! - 1);
      if (window.get(lc)! < need.get(lc)!) have--;
      L++;
    }
  }

  return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);
}

Note → The window boundaries come from filtered[L][0] and filtered[R][0] — the real indices in s — so the measured length still spans the irrelevant characters between them. Only the iteration count shrinks: when t is small the inner loop touches far fewer positions than the plain window does.

ALT 2 Brute force — check every substring

O(|s|² · |Σ|) time, O(|Σ|) space

Generate every [i..j] substring and test whether its character counts cover t — simple, but quadratic.

approach-3.ts
function minWindow(s: string, t: string): string {
  if (t.length === 0 || s.length < t.length) return '';

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

  // Does the count map 'have' cover every requirement in 'need'?
  const covers = (have: Map<string, number>): boolean => {
    for (const [ch, n] of need) {
      if ((have.get(ch) ?? 0) < n) return false;
    }
    return true;
  };

  let bestLen = Infinity;
  let bestStart = -1;

  for (let i = 0; i < s.length; i++) {
    const have = new Map<string, number>();
    // Extend the right edge, growing the count map incrementally.
    for (let j = i; j < s.length; j++) {
      const c = s[j];
      have.set(c, (have.get(c) ?? 0) + 1);

      if (j - i + 1 >= t.length && covers(have)) {
        const len = j - i + 1;
        if (len < bestLen) {
          bestLen = len;
          bestStart = i;
        }
        break; // shortest window starting at i is found; move on
      }
    }
  }

  return bestStart === -1 ? '' : s.slice(bestStart, bestStart + bestLen);
}

Note → Reusing the same have map across the inner j loop avoids re-counting from scratch, but each covers call still scans the distinct characters of t, giving the extra |Σ| factor. The early break stops at the shortest window per start index, yet the outer pass over every start keeps it quadratic.

MNEMONIC The one-liner

"Expand R until you HAVE what you NEED, then contract L to shrink — record the best window each time."

TRIGGERS When you see _ → reach for _

"shortest / smallest window containing …"	expand-right / contract-left sliding window
must contain all chars of t (with multiplicity)	need map + have/required counter
increment have only when count exactly hits requirement	window.get(c) === need.get(c)
"permutation in string" / "find all anagrams"	same template, fixed-size window variant

SKELETON The reusable shape

skeleton.ts
const need = new Map<string, number>();
for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
const required = need.size;
const window = new Map<string, number>();
let have = 0, L = 0, bestLen = Infinity, bestL = 0, bestR = 0;

for (let R = 0; R < s.length; R++) {
  const c = s[R];
  window.set(c, (window.get(c) ?? 0) + 1);
  if (need.has(c) && window.get(c) === need.get(c)) have++;

  while (have === required) {
    if (R - L + 1 < bestLen) { bestLen = R - L + 1; bestL = L; bestR = R; }
    const lc = s[L];
    window.set(lc, window.get(lc)! - 1);
    if (need.has(lc) && window.get(lc)! < need.get(lc)!) have--;
    L++;
  }
}
return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);

FLASHCARDS Tap to flip

What does the `have` counter track?

The number of distinct characters whose window count has reached (or exceeded) the required count from t.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the sliding-window solution for minWindow(s, t)?

QUESTION 02

Given t = "AA", when should have be incremented for character 'A'?

QUESTION 03

What does `required = need.size` represent (as opposed to `t.length`)?

QUESTION 04

When contracting from the left, what condition triggers decrementing have?

QUESTION 05

For s="ADOBECODEBANC", t="ABC", what is the minimum window?

QUESTION 06

The `while (have === required)` inner loop can run many times for a single R. What is the total number of times L advances across the entire algorithm?

QUESTION 07

What is returned when s does not contain all characters of t?

QUESTION 08

#76 · Minimum Window SubstringFind the shortest substring of s that contains every character of t. A sliding window with a need/have counter solves it in O(|s| + |t|) time.Which algorithmic approach does this primarily use?

QUESTION 09

#76 · Minimum Window SubstringFind the shortest substring of s that contains every character of t. A sliding window with a need/have counter solves it in O(|s| + |t|) time.Which implementation correctly solves it?

PROBLEM What we're solving

KEY IDEA Expand right until valid; contract left to minimize

RECIPE Expand → record → contract → repeat

COST Complexity & trade-offs

RUN IT Expand right, contract left, record the best

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Sliding Window

ALT 1 Filtered-index sliding window

ALT 2 Brute force — check every substring

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _