Minimum Window Substring

The problem. Given strings s and t, return the shortest substring of s that contains every character of t, counting duplicates (if t has two a's, the window needs two a's). If there is none, return "". The answer is unique when it exists.

Example

s = "ADOBECODEBANC", t = "ABC"   ->  "BANC"
s = "a", t = "a"                 ->  "a"
s = "a", t = "aa"                ->  ""     (s has only one "a")

The idea: grow until it fits, then shrink while it still fits

This is the variable-size window, used to find the shortest valid window. Move right to take in characters until the window covers t. Then move left to drop characters for as long as the window still covers t, recording each covering window's length. When dropping a character breaks the cover, go back to growing. Every character enters once and leaves once.

The bookkeeping is what makes it O(1) per step. need[ch] says how many more copies of ch the window still lacks — it can go below zero when the window holds spare copies. missing is the total still lacking: the window covers t exactly when missing == 0, so there's never a need to compare whole count tables.

1. Brute force: the shortest covering window from every start

From each start, extend to the right until the window covers t; that's the shortest one from this start. Keep the best over all starts.

1function minWindow(s, t) {2  const need = new Map();3  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);4  let best = "";5  for (let i = 0; i < s.length; i++) {6    const have = new Map();7    let covered = 0;                                 // distinct characters with enough copies8    for (let j = i; j < s.length; j++) {9      const ch = s[j];10      have.set(ch, (have.get(ch) ?? 0) + 1);11      if (have.get(ch) === need.get(ch)) covered++;12      if (covered === need.size) {                   // s[i..j] covers t: the shortest from i13        if (best === "" || j - i + 1 < best.length) best = s.slice(i, j + 1);14        break;15      }16    }17  }18  return best;19}

Time O(n²), space O(1) beyond the answer (the counters have 128 slots, for ASCII). Each start rescans the characters the previous start already counted.

2. Sliding window with a missing-count

1function minWindow(s, t) {2  const need = new Map();                            // char -> how many more the window needs3  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);4  let missing = t.length;                            // characters of t not yet covered5  let left = 0, bestStart = 0, bestLen = Infinity;6  for (let right = 0; right < s.length; right++) {7    const ch = s[right];8    if (need.has(ch)) {9      if (need.get(ch) > 0) missing--;               // this one was still needed10      need.set(ch, need.get(ch) - 1);                // (below 0 means a spare copy)11    }12    while (missing === 0) {                          // the window covers t: try to shrink it13      if (right - left + 1 < bestLen) {14        bestStart = left;15        bestLen = right - left + 1;16      }17      const out = s[left++];18      if (need.has(out)) {19        need.set(out, need.get(out) + 1);20        if (need.get(out) > 0) missing++;            // dropped a character we still needed21      }22    }23  }24  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);25}

Time O(n + m), space O(1) for n = |s| and m = |t|: counting t is O(m), and left and right each pass over s once. (The Java and C++ versions use a 128-slot array instead of a map: characters outside t simply go negative and never matter.)

Comparing the approaches

This is the hardest of the window problems because it combines everything: counts with duplicates, a single number that says valid or not, and a shrink loop. If you can explain missing, you can do the rest.

Edge cases to test

Variations