Faangprep Logo
Log inStart free
Browse curriculum

Minimum Window Substring

Find the shortest part of s that contains every character of t, duplicates included, with a window that grows until it covers t and shrinks while it still does.

HardSolve on LeetCode

Problem Understanding

Minimum Window Substring: given strings s and t, return the shortest substring of s that contains every character of t, including duplicates. If no substring does, return "".

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

Attempt 1: Check Every Substring

Try every start and every end, and test whether that substring contains t: O(|s|²) substrings, each checked in O(|s|) or with counts — O(|s|³) or O(|s|²) at best. Most of that work is repeated: the substring starting one index later shares almost everything with the one before it.

The Intuition: Grow Until Covered, Shrink While Covered

Two facts make a sliding window work:

  1. If s[left..right] covers t, any longer window containing it does too — so there is no point extending a covering window.
  2. If s[left..right] does not cover t, no shorter window ending at right does either — so there is no point shrinking an uncovered one.

So right extends until the window covers t; then left advances while it still covers t, recording the shortest. To test coverage in O(1), keep need[c] — how many more of c the window needs, negative for spare copies — and missing, how many characters of t are still uncovered. The window covers t exactly when missing == 0.

Interactive Walkthrough

The window is framed between L and R: dashed while it is missing something, solid once it covers t. The need map beside it ticks each character off as it is satisfied. Watch the frame grow to "ADOBEC", lose the A, regrow, and shrink down to "BANC".

Dry Run Table

Input: s = "ADOBECODEBANC", t = "ABC" (the moments the window changes state)

right Event Window missing Shortest
0–5 Read A, B, C ADOBEC 0 ADOBEC (6)
— Drop A at 0 DOBEC 1 ADOBEC
6–10 Read up to A at 10 DOBECODEBA 0 ADOBEC
— Drop D, O, spare B, E CODEBA 0 ADOBEC (not shorter)
— Drop C at 5 ODEBA 1 ADOBEC
11–12 Read N, C ODEBANC 0 ADOBEC
— Drop O, D EBANC 0 EBANC (5)
— Drop E BANC 0 BANC (4)
— Drop B at 9 ANC 1 BANC

right has reached the end, so return "BANC".

The Solution Template

Counts of what is still needed, and one integer for how much.

Minimum Window Substring Code
1var minWindow = function(s, t) {
2    const need = new Array(128).fill(0);
3    for (const c of t) need[c.charCodeAt(0)]++;
4    let missing = t.length, left = 0, start = 0, size = Infinity;
5    for (let right = 0; right < s.length; right++) {
6        const ch = s.charCodeAt(right);
7        if (need[ch] > 0) missing--;
8        need[ch]--;
9        while (missing === 0) {
10            if (right - left + 1 < size) {
11                start = left;
12                size = right - left + 1;
13            }
14            const out = s.charCodeAt(left);
15            need[out]++;
16            if (need[out] > 0) missing++;
17            left++;
18        }
19    }
20    return size === Infinity ? "" : s.slice(start, start + size);
21};

Edge Cases & Common Mistakes

  • No covering window (s = "a", t = "aa"): missing never reaches 0 — return "".
  • Duplicates in t: t = "AAB" needs two As; counting distinct characters instead of occurrences gives wrong answers.
  • Spare copies: a second B when t needs one drives need['B'] negative; dropping it later must not raise missing.
  • Comparing two maps on every step: correct but slower; missing makes the coverage test O(1).
  • Case sensitivity: 'a' and 'A' are different characters.

Summary

Extend right until the window covers t, then shrink from left while it still does, recording the shortest. need counts what is still wanted and missing makes coverage an O(1) check. O(|s| + |t|) time, O(k) space.

Previous

Longest Repeating Character Replacement

Next

Overview (Fixed Length)

The approach, step by step

  1. Count t

    need[c] = occurrences of c in t; missing = len(t); left = 0.

  2. Extend right

    For each character, decrement missing if need[c] > 0, then decrement need[c].

  3. Shrink while covered

    While missing == 0, record the window if it is the shortest, then drop s[left]: increment its need, and increment missing if that need becomes positive.

  4. Return

    Return the shortest window recorded, or an empty string if none covered t.

Frequently asked questions

How does the sliding window solve Minimum Window Substring?

Move right one character at a time until the window contains every character of t. Then, while it still does, record it if it is the shortest so far and drop characters from the left. When a drop uncovers t, go back to extending. Each index enters and leaves the window at most once.

What is the 'missing' counter for?

It counts how many characters of t the window still lacks, duplicates included. need[c] holds how many more of c are needed; reading c decrements missing only while need[c] is positive, and dropping c increments it only when need[c] climbs back above zero. The window covers t exactly when missing is 0, so the check is O(1) instead of comparing two maps.

What is the time complexity of Minimum Window Substring?

O(|s| + |t|). Counting t takes O(|t|); then left and right each move forward at most |s| times, with O(1) work per move. The counts use O(k) space for k distinct characters — O(1) for a fixed alphabet.