Minimum Window Substring

Given two strings s and t, return the shortest substring of s that contains every character of t, counting multiplicities (if t has two as, the window must too).

If no such window exists, return the empty string "". When several shortest windows exist, return the one that starts earliest.

Hints

· Stuck? Reveal one nudge at a time.

Grow the window until it contains all of t, then try to shrink it from the left.

Track a 'need' count per character and a single 'missing' counter for how many are still unmet.

When missing hits zero the window is valid; record it as you shrink while it stays valid.

Common doubts

It counts how many required characters (with multiplicity) are still unmet. It drops when you consume a still-needed character and rises when shrinking would remove one — so validity is just 'missing == 0'.

Characters not in t, or extra copies beyond what t needs, don't reduce the requirement. Their need count is <= 0, so they leave missing unchanged.

Inside the shrink loop, while the window is valid — that's exactly when you have a covering window and are minimizing its length.

Interview follow-ups

· What an interviewer asks next.

Track how many times the minimum length is achieved during the shrink phase, resetting when a strictly smaller window appears.

Use a hash map instead of a fixed array for need/have; the algorithm is identical and stays O(n + m).

Fun facts

Minimum Window Substring is the canonical 'shortest window' problem — the mirror image of all the 'longest window' problems in this chapter.
The single 'missing' counter trick — collapsing a whole map comparison into one integer — recurs in anagram and permutation-in-string problems.

Asked at

AmazonGoogleMetaMicrosoftUber

Frequently Sometimes Occasionally

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: BANC
The shortest window of s containing A, B, and C is "BANC".

Example 2

Input: s = "a", t = "aa"
Output: 
s has only one 'a' but t needs two, so no valid window exists.

Constraints

- 1 <= s.length, t.length <= 10^5 - s and t consist of uppercase and lowercase English letters.

This is the "shortest window" mirror of the chapter. Expand the right edge until the window covers all of t, then contract the left edge as far as it stays valid, recording the smallest valid window along the way. A "need" count plus a single missing counter tells you validity in O(1).

Prerequisites

Before you start

· Concepts used directly in the solution.

Variable window. Growing until valid, then shrinking while still valid.

Need / have counts. A map of required character counts, and how many are still unmet.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“Do duplicate characters in t matter?”

Yes — the window must contain at least as many of each character as t has.

“What if no window covers t?”

Return the empty string.

Ties

“If several windows tie for shortest?”

Return the earliest-starting one (the problem's answer is unique for its tests).

The ideal opening — say it like this

I count what characters t needs, and a single 'missing' counter for how many are still unmet.

I extend the right edge, decrementing needs; when missing hits zero the window covers t.

Then I shrink from the left while still valid, recording the smallest window each time.

Understand the problem

Worked example — s = "ADOBECODEBANC", t = "ABC"

expand to "ADOBEC" -> valid, shrink -> "DOBEC"? no, need A... best "ADOBEC" (6)
continue... eventually window "BANC" is valid and length 4
answer: "BANC"

Key observations

1Aha

A single 'missing' counter checks validity in O(1)

Rather than comparing whole maps, track how many required characters are still unmet. The window is valid exactly when missing == 0.

2Aha

Grow to valid, then shrink while valid

The right pointer only expands; when the window becomes valid, the left pointer contracts as far as it can while remaining valid, capturing the smallest window ending at that right.

3Aha

Record the smallest, earliest window

Update the best only on a strictly smaller length. Because windows are discovered in increasing right order, ties keep the earliest start automatically.

Brute force vs optimal

	Shortest from each start	Grow/shrink window
Idea	From each i, extend to the first window covering t	Expand to valid, contract while valid, track min
Time	O(n^2 * sigma)	O(n + m)
Space	O(sigma)	O(sigma)

The brute re-scans and re-checks coverage from every start; the window advances both pointers forward with an O(1) validity check. Full code is in the Approaches selector below.

Summary

Key takeaway

Track a need map and a missing counter. Expand right until missing == 0 (window covers t), then shrink left while it stays valid, recording the smallest window. Both pointers move forward, so it's O(n + m) — the canonical shortest-window template.

need = counts of t; missing = len(t); left = 0; best = ""
for right in 0 .. n-1:
    if need[s[right]] > 0: missing -= 1
    need[s[right]] -= 1
    while missing == 0:
        record window if smaller
        need[s[left]] += 1
        if need[s[left]] > 0: missing += 1
        left += 1
return best