Minimum Window Substring

Strings · Sliding Window · LeetCode 76 · Hard

Given two strings s and t, return the smallest substring of s that contains every character in t (including duplicates). If no such window exists, return "".
Two pointers L and R define a sliding window. Expand R to include characters until the window is valid (contains all of t), then shrink L to minimize it. A formed counter tracks how many unique characters in t are fully satisfied, giving an O(1) validity check.

examples s = "ADOBECODEBANC", t = "ABC" → "BANC"
s = "a", t = "a" → "a"
s = "a", t = "aa" → "" (impossible)

s = "ADOBECODEBANC", t = "ABC" — sliding window

formed 0 / 3

best —

length —

expanding R shrinking L

step 0 / 0

in window

needed (in t)

R just added

L removing

best window

Press Next step to begin. Expand R until the window contains all characters of t, then shrink L to minimize.

State Snapshot

—

formed

0 / 3

best

—

Pseudocode

time: O(|s| + |t|) space: O(|Σ|) pattern: sliding window

▼ Notes & Key Insight

Key Insight

The formed counter tracks how many unique characters in t meet their required count in the current window. This turns the "is the window valid?" check from O(k) per step into O(1) — the difference between an O(n·k) algorithm and a true O(n) one.

Why Two Pointers?

Once the window is valid, any further expansion of R only makes it larger, never smaller. So we shrink from L until it's no longer valid, then resume expanding R. Each pointer only moves right — every character is visited at most twice.

Complexity

Time: O(|s| + |t|) — build the need map in O(|t|), then each character in s is added and removed at most once.
Space: O(|Σ|) — two hash maps bounded by the character set size.

Pattern

Sliding Window with frequency maps. The same expand-then-shrink skeleton applies to Longest Substring Without Repeating Characters (LC #3), Permutation in String (LC #567), and Find All Anagrams (LC #438).

Edge Cases

• t longer than s → impossible, return ""
• Duplicate characters in t → need map tracks exact counts, not just presence
• t is a single character → find first occurrence in s

Common Mistake

Incrementing formed every time a needed character is added instead of only when its count exactly reaches the required amount. Over-counting makes validity checks incorrect.