4.6.5 — Minimum Window Substring

LeetCode 76 · Hard · ★ Blind 75

The problem

Return the shortest substring of s that contains every character of t, including repeats. Return "" if there is none.

s = "ADOBECODEBANC", t = "ABC"   →  "BANC"
s = "a", t = "aa"                →  ""     (only one a available, two needed)

Both strings may contain any English letters, upper or lower case. Up to 100,000 characters.

"Including repeats" is the detail that decides the solution. If t is "AABC" the window needs two A's, not one. That is why this is a counting problem and not a set problem.

The pattern

Same window as before, but the target has flipped. Previous problems wanted the longest window satisfying a condition, so you recorded the answer after repairing an invalid window. Here you want the shortest valid window, so:

• Extend the right edge until the window becomes valid.
• Then shrink from the left as long as it stays valid, recording the answer each time.
• Stop shrinking the moment it breaks, and go back to extending.

The shape is the mirror image: grow until valid, then shrink while still valid.

Tracking validity without rechecking everything

The naive check is "does the window contain enough of every character in t", which costs O(52) per step. There is a cleaner way that costs O(1), and it is the idea worth taking from this problem.

Keep two numbers:

• required — how many distinct characters of t still need their full count met.
• For each character, how many the window currently holds.

When a character's window count reaches exactly its required count, one requirement is satisfied, so required drops by one. When it falls below again, required goes back up.

The window is valid exactly when required == 0. One integer comparison.

The word exactly is doing real work. If the window holds three A's and needs two, adding a fourth changes nothing about validity, so required must not move. Only the transition through the boundary counts.

The solution

Python

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(t) > len(s):
            return ""

        need = Counter(t)
        required = len(need)          # distinct characters still unsatisfied
        window = {}

        left = 0
        best_len = float('inf')
        best_start = 0

        for right in range(len(s)):
            c = s[right]
            window[c] = window.get(c, 0) + 1
            if c in need and window[c] == need[c]:      # exactly met
                required -= 1

            while required == 0:                        # valid — try to shrink
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_start = left

                lc = s[left]
                window[lc] -= 1
                if lc in need and window[lc] < need[lc]:   # just broke it
                    required += 1
                left += 1

        return "" if best_len == float('inf') else s[best_start:best_start + best_len]

TypeScript

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

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

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

  let left = 0, bestLen = Infinity, bestStart = 0;

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

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

  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
}

Four things to notice.

required counts distinct characters, not total characters. For t = "AABC" it starts at 3, not 4, because there are three distinct letters. Getting this wrong is the most common bug in this problem.

window[c] == need[c] uses ==, not >=. Only the exact moment of satisfying a requirement should decrement required. Using >= would decrement again on every extra copy.

window[lc] < need[lc] uses <, mirroring it. Only the moment of dropping below breaks the requirement.

The answer is recorded inside the shrink loop, before shrinking. At that instant the window is valid, and every further shrink either keeps it valid — in which case it is recorded again, smaller — or breaks it. So every valid window is measured.

Storing best_start and best_len rather than slicing the string each time matters: slicing inside the loop would be O(n) per step and would quietly make the whole solution quadratic. This is the "track index pairs, do not cut substrings" discipline from 4.2.

Trace

s = "ADOBECODEBANC", t = "ABC", so need = {A:1, B:1, C:1} and required = 3.

event	window	required	best
right reaches C at index 5	ADOBEC	0	"ADOBEC" (6)
shrink: drop A	DOBEC	1	—
right reaches A at index 10	DOBECODEBA	0	still 6, this is longer
shrink to ODEBA… then to BANC later			"BANC" (4)

The final answer is "BANC".

Complexity

O(n + m) time. Each pointer moves forward at most n times over the entire run, and every other operation is O(1) thanks to the required counter.

O(m) space for the two maps, where m is the number of distinct characters in t.

Where this goes next

This is the reference implementation for the shortest valid window family:

• Minimum Size Subarray Sum — the shortest subarray with sum at least k, for positive numbers. Same skeleton, validity is a running sum.
• Substring with Concatenation of All Words — the same counting idea over whole words instead of characters.
• Smallest Range Covering Elements from K Lists — the same "cover everything, then shrink" idea across several sorted lists, using a heap.

The general rule, and it is worth memorising as a pair:

• Longest valid window: shrink while invalid, record after the loop.
• Shortest valid window: shrink while valid, record inside the loop.

Knowing which one a problem is asking for, before you write anything, is most of the battle.

What the interviewer will push on

"Why does required count distinct characters?" Because one character's requirement is satisfied once, no matter how many copies it needs. Counting total characters would need a different update rule and gets tangled fast.

"Why == and not >= when decrementing?" So that extra copies beyond the requirement do not decrement it again.

"Prove this is O(n)." Both pointers only move forward and never pass each other, so together they take at most 2n steps.

"What if t has duplicate characters?" It already works — that is exactly what the counts handle. This question is checking whether you used a set instead of a counting map.

"Can you return the window without slicing inside the loop?" Yes, and you should: store the start index and length, slice once at the end.

One thing to volunteer: state the two window shapes before coding. "For the longest window I shrink while invalid; for the shortest I shrink while valid and record inside the loop. This is the second one." That framing tells the interviewer you have a method rather than a memorised solution.

Next: 4.6.6 Sliding Window Maximum — a fixed window again, but now you must know its maximum at every step, which needs a different structure entirely.