Minimum Window Substring

Find the smallest substring that contains all characters of t.

Find the smallest substring in s that contains all characters of t, including multiplicity. The challenge is not finding a valid window once, but shrinking it without losing required coverage.

StringSliding Window

Pattern fit

This is the classic coverage window: expand until every required character is satisfied, then shrink as much as possible while staying valid.

Key observation

The key state is not distinct count alone but how many required character frequencies have been fully satisfied.

Target complexity

O(n) / O(k)

How to break down the solution cleanly

Build a frequency map for t so you know how many of each character are required.

Expand the right pointer and decrease the need count for that character.

When all required characters are satisfied, try shrinking from the left while staying valid.

Each time the window is valid, compare it against the best answer so far.

Walk through one example

Example: s = "ADOBECODEBANC", t = "ABC".

The first valid window is "ADOBEC", but it is not minimal.

Continue expanding and shrinking until the window "BANC" is found.

At that point no shorter valid window exists, so answer is "BANC".

Reference implementation

Python

from collections import Counter

def minWindow(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    left = 0
    best_start = 0
    best_len = float("inf")

    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        while missing == 0:
            if right - left + 1 < best_len:
                best_start = left
                best_len = right - left + 1

            left_char = s[left]
            need[left_char] += 1
            if need[left_char] > 0:
                missing += 1
            left += 1

    if best_len == float("inf"):
        return ""

    return s[best_start:best_start + best_len]

TypeScript version

TypeScript

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
  }

  let missing = t.length;
  let left = 0;
  let bestStart = 0;
  let bestLength = Number.POSITIVE_INFINITY;

  for (let right = 0; right < s.length; right += 1) {
    const char = s[right];
    const currentNeed = need.get(char) ?? 0;
    if (currentNeed > 0) {
      missing -= 1;
    }
    need.set(char, currentNeed - 1);

    while (missing === 0) {
      if (right - left + 1 < bestLength) {
        bestStart = left;
        bestLength = right - left + 1;
      }

      const leftChar = s[left];
      need.set(leftChar, (need.get(leftChar) ?? 0) + 1);
      if ((need.get(leftChar) ?? 0) > 0) {
        missing += 1;
      }
      left += 1;
    }
  }

  return Number.isFinite(bestLength)
    ? s.slice(bestStart, bestStart + bestLength)
    : "";
}

What to pay attention to in the code

codeUse a matched counter to represent how many required characters are fully satisfied.
codeThe window stops being valid exactly when removing left makes one required count positive again.