Minimum Window Substring

SLIDING WINDOW · HARD

Builds on Day 5: Sliding Window Pattern

This problem’s optimal solution is a variable-size sliding window with two pointers; read that lesson first if expanding/shrinking a window instead of using fixed bounds is still a new idea.

The problem

Given two strings s and t, find the smallest contiguous substring of s that contains every character of t — including matching duplicate counts. If t asks for two 'a's, the window has to actually contain two 'a's, not just one. If no such window exists, return "". For example, s="ADOBECODEBANC", t="ABC" → the shortest window covering all of A, B, and C is "BANC" (length 4) — shorter candidates like "ADOBEC" are valid too, just not minimal. s="a", t="aa" → "", because s only has one 'a' total, and no substring of it can ever contain two.

Solution 1: Brute force — check every substring, verify each with a frequency map

The most literal reading of the problem: try every possible substring of s (every start/end pair, O(n²) of them), and for each one, build a frequency map of its characters and compare it against t’s frequency map to decide whether it’s valid. Track the shortest valid one seen. Building and comparing a frequency map for a substring is itself O(n) work, so the total cost stacks to O(n²) × O(n) = O(n³) — checking every substring, and for each one, re-reading every character in it from scratch.

function minWindowBrute(s, t) {
  if (t.length === 0 || s.length === 0 || t.length > s.length) return '';
  const need = {};
  for (const ch of t) need[ch] = (need[ch] || 0) + 1;

  let best = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const sub = s.slice(i, j + 1);
      if (sub.length < t.length) continue;

      const have = {};
      for (const ch of sub) have[ch] = (have[ch] || 0) + 1;

      let ok = true;
      for (const ch in need) {
        if ((have[ch] || 0) < need[ch]) { ok = false; break; }
      }
      if (ok && (best === '' || sub.length < best.length)) {
        best = sub;
      }
    }
  }
  return best;
}

Line by line:

• t.length > s.length is a fast-fail: t can never fit inside a shorter s, so there’s no point trying any substring at all.
• The nested i/j loops generate every contiguous substring of s — O(n²) of them in total.
• if (sub.length < t.length) continue; skips substrings that are provably too short to contain t’s characters, but this is a minor pruning, not a change in asymptotic complexity — the O(n²) substring count still dominates.
• Building have by iterating every character of sub, then checking every key of need against it, is O(n) work — and it happens fresh, from nothing, for every single one of the O(n²) substrings.
• best === '' || sub.length < best.length only replaces the current best with a strictly shorter valid window — ties keep the earlier (leftmost-found) one, which matches the problem’s “the” smallest window being any one of possibly several equal-length answers.

Interactive visualization

s = "ADOBECODEBANC", t = "ABC" — watch every substring get checked

Press Play or Step to begin.

Step 0 / 68

▶ Play⏭ Step↺ Reset

This animation traces s="ADOBECODEBANC", t="ABC" — LeetCode’s own canonical example (expected: "BANC"), verified before any HTML was written. Every substring of length ≥ 3 gets checked; watch how many are tried before "BANC" is confirmed as the shortest.

Complexity

Time	Space	Approach
O(n³)	O(n)	O(n²) substrings, each verified with a fresh O(n) frequency-map comparison

Solution 2: Optimal — variable-size sliding window with two pointers

Build a frequency map need of t. Expand a right pointer across s one character at a time, tracking a running frequency map of the current window. The key bookkeeping trick: instead of re-comparing the entire window map against need on every step, track a single counter, have — how many of need’s distinct characters are currently satisfied at exactly the required count. A character becomes “satisfied” the moment the window’s count for it first reaches (not exceeds — exactly reaches) need’s count for it; have increments only at that exact crossing, never again while the count keeps climbing past it. Once have === required (every distinct character in t is covered), the window is fully valid — greedily shrink it from the left for as long as it stays valid, recording the best (shortest) window at each valid contraction, then resume expanding right.

The reason this is O(n + m) and not something quadratic: right only ever moves forward, one step per outer-loop iteration, so it makes at most n total moves across the entire run. left only ever moves forward too — even though its shrink loop looks nested, left can never advance past right, and it never resets backward. So across the whole algorithm, left also makes at most n total moves, not n moves per position of right. Two pointers that each independently move forward at most n times, total, add up to O(n) work overall — not O(n²) — plus O(m) to build need from t up front.

s = "ADOBECODEBANC", t = "ABC" — two pointers sweep once each, O(n) total

Press Play or Step to begin.

Step 0 / 33

▶ Play⏭ Step↺ Reset

Same s="ADOBECODEBANC", t="ABC" as Solution 1, so you can directly compare step counts: watch right and left each sweep across s once, versus the brute force’s dozens of independent substring checks above.

function minWindowOptimal(s, t) {
  if (t.length === 0 || s.length === 0 || t.length > s.length) return '';

  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
  const required = need.size;

  const window = new Map();
  let have = 0;
  let left = 0;
  let bestLen = Infinity;
  let bestLeft = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (need.has(ch)) {
      window.set(ch, (window.get(ch) || 0) + 1);
      if (window.get(ch) === need.get(ch)) have++;
    }

    while (have === required) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestLeft = left;
      }
      const lch = s[left];
      if (need.has(lch)) {
        if (window.get(lch) === need.get(lch)) have--;
        window.set(lch, window.get(lch) - 1);
      }
      left++;
    }
  }

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

Line by line:

• need maps each character of t to how many copies it requires; required = need.size is the count of distinct characters, not the total character count of t — that distinction is exactly what have tracks against.
• if (window.get(ch) === need.get(ch)) have++; is the bookkeeping detail the whole algorithm hinges on: this fires exactly once per character, at the instant its window count first reaches its required count — not every time the count changes, and not when the count later overshoots past what’s needed.
• while (have === required) — not an if — is what lets the window shrink as far as it can from a single expansion of right: it keeps contracting, recording a new best each time, until removing one more character would break validity.
• if (window.get(lch) === need.get(lch)) have--; mirrors the increment logic in reverse: have only decrements at the instant a needed character’s count drops below what’s required, checked before the count is actually decremented on the next line.
• bestLen === Infinity at the end distinguishes “no valid window was ever found” from “the valid window happened to have length 0” (which can’t happen here, but the sentinel makes the empty-result case explicit rather than accidental).

Complexity

Time	Space	Approach
O(n + m)	O(n + m)	Variable-size sliding window; right and left each move forward at most n times total, need/window maps bounded by distinct characters

Complexity comparison

Solution	Time	Space
Brute force (every substring, fresh frequency check)	O(n³)	O(n)
Optimal (two-pointer sliding window)	O(n + m)	O(n + m)

This is a genuine, dramatic asymptotic improvement — cubic down to linear — not a same-complexity relabeling. The brute force pays O(n) to re-verify every one of O(n²) candidate substrings from scratch; the sliding window instead carries its validity state (have) forward incrementally as the window moves, so each character is only ever added to or removed from the running count a constant number of times across the entire scan.

Interview corner

The shrink step is a while loop nested inside a for loop — that looks like O(n²) at a glance. Why is the real bound O(n)?

• The nesting is misleading because left is never reset — its position carries over from one iteration of the outer loop to the next, it only ever increases.
• Since left can never exceed right, and both only move forward, the total number of times left advances across the entire run — summed over every iteration of the outer loop — is bounded by n, not by n per outer-loop iteration.
• This is the classic “amortized” argument for two-pointer/sliding-window algorithms: count total pointer movement across the whole algorithm, not per-iteration work in isolation — two pointers that each independently move forward at most n times total add up to O(n), never O(n²).

Why track a single have counter instead of just comparing the entire window map against need on every step?

• Comparing two full maps (checking every key of need against window) is itself an O(m) operation — doing that on every one of the n expansions (and again on every shrink) would reintroduce a multiplicative factor, undoing the whole point of the optimization.
• have is an O(1)-to-check integer that gets nudged up or down incrementally, exactly when a single character’s status flips between “satisfied” and “not satisfied” — it never requires re-scanning the rest of the map to stay correct.
• This is a general pattern worth recognizing beyond this problem: whenever “is the current state fully valid?” would otherwise require an O(m) full-structure comparison, look for a single incrementally-maintained counter that captures the same information in O(1) per update.

Why does have increment specifically when a character’s window count equals its needed count — not when the window count is merely > 0, and not every time the count changes?

• Using > 0 would be wrong for duplicate-count requirements: if t needs two 'a's, seeing a single 'a' doesn’t satisfy that requirement yet — the window isn’t valid for 'a' until it has two.
• Incrementing on the exact-equality crossing, rather than on every count change, is what keeps have bounded by required (the number of distinct characters) instead of drifting arbitrarily high as a character’s count keeps climbing past what’s needed — a common source of subtle off-by-N bugs in this exact pattern.
• The decrement side mirrors this precisely: have only drops when a character’s count falls below its needed count during a shrink, checked before the count is actually decremented on the next line.

↳ Common follow-up: “What breaks if you swap the order — decrement the window count, then check the condition, instead of checking first?” The comparison would read the count after it already dropped below need, so the count could sail two values past the threshold in a single step without have ever registering the crossing — that’s exactly why the check happens before the mutation on both the expand and shrink sides.

Trick question — what does this log?

const counts = {};
counts['z'] = 1;
counts['3'] = 1;
counts['a'] = 1;
counts['1'] = 1;
console.log(Object.keys(counts));

Answer: ['1', '3', 'z', 'a'] — NOT insertion order ['z', '3', 'a', '1'].

Plain objects treat non-negative integer-like string keys ('1', '3') as special “array index” keys, and always enumerate those first, in ascending numeric order — regardless of when they were assigned. Only after that do the remaining string keys ('z', 'a') appear, in true insertion order.

A real Map — like need and window in the solution above — has no such carve-out: it always preserves insertion order for every key type, digit-like or not.

⚠ Trap: LeetCode’s stated constraints for this problem only allow English letters in s and t, so this exact reordering can’t bite the solution above as written. But the moment this pattern gets reused on a string containing digit characters — a very plausible generalization — a plain-object frequency map would silently reorder itself the instant a digit key is inserted, which is precisely why reaching for Map here, rather than {}, is the safer default habit, not just a stylistic choice.

Quiz

1. The shrink loop is nested inside the expand loop, which looks like O(n²) at first glance. What’s the real time bound, and why?

• O(n) — left never resets and moves forward at most n times total across the whole run, not per outer-loop iteration
• O(n²) — the nested loop structure means it really is quadratic, just with a small constant
• O(n log n) — the shrink loop behaves like a binary search on the window size

Answer: O(n) — left never resets and moves forward at most n times total across the whole run, not per outer-loop iteration. The key insight is amortized analysis: sum total pointer movement across the whole algorithm, not per-iteration work in isolation.

2. Why does the optimal solution maintain a have counter instead of comparing the entire window map against need on every step?

• A full map comparison is O(m) per check; have is an O(1) integer nudged only when a character’s satisfied/not-satisfied status actually flips
• Because Map objects don’t support any form of equality comparison at all
• It’s a purely stylistic preference with no effect on performance

Answer: A full map comparison is O(m) per check; have is an O(1) integer nudged only when a character’s satisfied/not-satisfied status actually flips. Comparing maps on every step would reintroduce a multiplicative factor.

3. Why does have increment when a character’s window count exactly EQUALS its needed count — not when the count is merely greater than 0?

• Because a single occurrence doesn’t satisfy a character that needs multiple copies — the exact-equality crossing is what correctly handles duplicate counts in t
• Exact equality checks execute faster in JavaScript than greater-than checks
• There’s no real reason — greater-than-0 would work identically for every possible input

Answer: Because a single occurrence doesn’t satisfy a character that needs multiple copies — the exact-equality crossing is what correctly handles duplicate counts in t.

4. What is the brute-force solution’s real time complexity, and why?

• O(n³) — O(n²) candidate substrings, each verified with a fresh O(n) frequency-map comparison
• O(n²) — generating every substring is the only real cost; the frequency check is effectively free
• The same O(n + m) as the optimal solution — it’s just a different technique, not a slower one

Answer: O(n³) — O(n²) candidate substrings, each verified with a fresh O(n) frequency-map comparison. It’s a real, dramatic asymptotic gap versus the optimal solution’s O(n + m).

5. On both the expand and shrink sides, the code checks a character’s count against need/window BEFORE updating that count. What would break if the check happened after the update instead?

• The count could cross the threshold without have ever registering it, since the equality check would already be looking at the post-update value
• Nothing — the order of the check and the update has no effect on correctness
• It would only be a minor performance regression, not a correctness bug

Answer: The count could cross the threshold without have ever registering it, since the equality check would already be looking at the post-update value. This breaks the have/required bookkeeping.