Frontend Beauty
ESC

Type to search the knowledge base.

Minimum Window Substring

Smallest window in s covering all of t — sliding window with need/have counts, O(|s| + |t|).

advanced3 min read
  • dsa
  • sliding-window
  • interview
  • Google
  • Meta

The problem

Given 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 none, return "".

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

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

Brute force

For every pair (i, j), check if s[i..j] covers t. O(n² · Σ) with counting — too slow for interviews once n is large.

Optimal: variable sliding window

  1. Count required frequencies from t (need map, required unique keys).
  2. Expand right, update window counts and formed when a char’s count hits need.
  3. While window is valid, shrink left, track best length/indices.
function minWindow(s: string, t: string): string {
  if (!t || s.length < t.length) return "";

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

  const window = new Map<string, number>();
  let formed = 0;
  let left = 0;
  let bestLen = Infinity;
  let bestStart = 0;

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

    if (need.has(ch) && window.get(ch) === need.get(ch)) {
      formed++;
    }

    while (left <= right && formed === required) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      const drop = s[left];
      window.set(drop, window.get(drop)! - 1);
      if (need.has(drop) && window.get(drop)! < need.get(drop)!) {
        formed--;
      }
      left++;
    }
  }

  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
}
Time O(
Space O(Σ) distinct chars in s and t

Critical detail

Increment formed only when counts become equal to need — not on every extra occurrence. Same for decrementing when dropping below need.

Edge cases

  • t longer than s → ""
  • t empty — clarify; usually not
  • Duplicates in t ("aa") need two as
  • Multiple valid windows — return any minimum length (LC: smallest window; if ties, the first found is fine)
  • Case sensitive

Common bugs

  • Treating multiset as set (ignoring counts)
  • Updating formed on every match not just threshold cross
  • Infinite shrink loop
  • Returning indices instead of substring

Interview delivery

  1. Cover multiset of t with shortest window of s.
  2. Expand right / shrink left pattern.
  3. need/have + formed counter.
  4. Trace ADOBECODEBANC / ABC.
  5. O(|s|+|t|).

Further reading