Hard

Minimum Window Substring

Expand to satisfy the requirement, then contract to minimize.

Approach

Count the characters you need. Expand the right edge until the window contains all of them, then contract the left edge as far as possible while still valid, recording the smallest such window. A 'need' counter lets you check validity in O(1) per step.

Time complexity

O(n)

Space complexity

O(alphabet)

Common mistake

Only expanding, never contracting — the minimum window requires shrinking whenever the constraint is still met.

Interactive walkthrough — step through it below, free and without an account

Problem

Given two strings s and t, find the shortest contiguous part of s that contains all characters from t with the required multiplicities. Return the empty string if no substring can satisfy the requirement.

Examples

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

The window BANC contains A, B, and C, and no shorter valid window exists.

Input: s = "a", t = "aa"

Output: ""

The source contains only one a, but two are required.

Problem

Given two strings `s` and `t`, find the shortest contiguous part of `s` that contains all characters from `t` with the required multiplicities. Return the empty string if no substring can satisfy the requirement.

Problem and Goal

Learning goal: Recognize the exact condition that makes a substring a valid candidate.

Core idea A candidate window is valid only when it contains every character in t with at least the required frequency. Extra characters are allowed, but missing even one required occurrence makes the window invalid. The task is therefore an optimization problem: maintain validity while minimizing the window length.

Algorithm plan

Count each character required by t in a map called need.
Maintain a window over s using left and right.
Track how many required character occurrences are still missing.
Expand until the window becomes valid, then shrink from the left.

Micro-example For t = "ABC", the requirement is one A, one B, and one C. The substring "ADOBEC" is valid even though it contains extra characters.

Pitfalls

Matching distinct character types is not enough when t contains duplicates.
A valid window may contain irrelevant characters that should be removed.
If no window satisfies the requirement, return "".

Recap

Validity is based on frequencies, not just set membership.
The answer must be contiguous.
We will search efficiently with two moving boundaries.

Problem and Goal

A candidate must satisfy every frequency

For `t = "ABC"`, a window is valid when it contains at least one `A`, one `B`, and one `C`. Extra characters such as `D`, `O`, and `E` do not hurt validity.

Validity means all required counts are met.

Expand, Then Contract

Learning goal: Understand why the sliding window alternates between expansion and contraction.

Core idea The right edge explores new characters until the current window satisfies the requirement. Once valid, moving the left edge is safe to try because every shorter valid window is a better candidate than the current one. Continue shrinking while validity survives; when it breaks, resume expanding.

Key insight

Expand to satisfy the requirement, then contract to minimize. The minimum window is discovered during contraction, not expansion.

Algorithm plan

Add s[right] to the window as right moves forward.
Decrease missing only when that character fills a still-needed occurrence.
While missing == 0, record the current range and remove s[left].
If removal creates a deficit, move right again.

Micro-example After reading ADOBEC, all of A, B, and C are present. Record it, remove A, and validity breaks; the next expansion must find another A.

Pitfalls

Do not stop after the first valid window.
Do not shrink only once; several left characters may be removable.
Record before removing the left character.

Recap

Expansion finds feasibility.
Contraction finds the best feasible boundary.
The loop invariant is that every recorded window is valid.

Expand, Then Contract

Move `right` until every required occurrence is present.

Read through `ADOBEC` to satisfy `ABC`.

Counting Requirements in O(1) Updates

Learning goal: Derive the constant-time validity check used by the sliding window.

Core idea Store required frequencies in need. A second map, often called window, stores frequencies inside the current range. The scalar missing starts at t.length; it decreases only when an incoming character contributes a required occurrence, and increases only when removing a necessary occurrence.

Algorithm plan

Build need from t and initialize missing = t.length.
For each right, increment the window count.
If window[ch] <= need[ch], decrement missing.
While missing == 0, update the best range.
Remove s[left]; if window[ch] < need[ch], increment missing.

Code

need = frequency(t)
left = 0, missing = length(t)
best = empty
for right from 0 to length(s) - 1:
    add s[right] and update missing
    while missing == 0:
        record the smallest valid window
        remove s[left] and update missing
        left += 1
return best

Micro-example For t = "AABC", missing begins at 4, not 3. The second A matters, so frequency counts preserve duplicate requirements.

Pitfalls

Decrementing missing for every matching character overcounts duplicates.
Removing an extra copy should not make the window invalid.
Use right - left + 1 for the inclusive window length.

Recap

missing == 0 is an O(1) validity test.
Frequency comparisons handle duplicates correctly.
Each pointer moves only forward.

Counting Requirements in O(1) Updates

State	Meaning	Example for t = "ABC"
`need`	Required frequencies	A: 1, B: 1, C: 1
`window`	Frequencies inside current range	Counts characters currently covered
`missing`	Required occurrences not yet covered	3 initially; 0 when valid

End-to-End Walkthrough

Learning goal: Trace how the pointers discover the answer BANC in ADOBECODEBANC.

Core idea The right pointer first reaches C at index 5, creating the valid window ADOBEC. Contraction removes dispensable characters until removing the leading A breaks validity. Later, the right pointer finds a new A and C, allowing a longer contraction that eventually exposes the shortest answer.

Algorithm plan

Expand across ADOBEC until missing becomes 0.
Record ADOBEC, then contract and lose validity after removing its only A.
Expand to the later A and C.
Contract repeatedly, recording shorter valid windows.
Finish with BANC, indices 9..12.

Micro-example At the end, the window EBANC is valid. Removing E, O, D, and E keeps it valid until only BANC remains; removing B would make it invalid.

Pitfalls

The first valid window is only a starting point.
Contraction can happen many times at one right position.
Always preserve the best range found before validity is lost.

Recap

First valid window: ADOBEC.
Final and smallest valid window: BANC.
Expansion and contraction together examine the string linearly.

End-to-End Walkthrough

Traces the concrete example from first satisfaction through final contraction.

Sliding window

1 / 13

Expand to index 0: A reduces missing from 3 to 2.

Pitfalls and Edge Cases

Learning goal: Avoid the implementation mistakes that make sliding-window solutions incorrect.

Core idea The most common error is expanding without contracting. That strategy can find a valid substring, but it cannot prove that the substring is minimal. Correct code must repeatedly shrink the left edge in a while loop whenever the current window remains valid.

Algorithm plan

Check the empty-result case naturally by leaving best unset.
Use frequency counts so repeated characters in t are enforced.
Update the answer before removing the leftmost character.
Distinguish a required character from an extra copy of that character.

Micro-example With s = "AA" and t = "A", after the second A arrives, shrinking should reduce AA to A. If the algorithm expands only, it incorrectly keeps a window twice as large as necessary.

Common pitfall

Only expanding, never contracting — the minimum window requires shrinking whenever the constraint is still met.

Pitfalls

Using if instead of while for contraction misses shorter valid windows.
Treating window[ch] > need[ch] as a deficit is incorrect; extras are harmless.
Returning the indices instead of the substring produces the wrong output format.

Recap

Contract immediately after validity is achieved.
Duplicates require frequency-aware updates.
Empty answers and repeated characters are important edge cases.

Pitfalls and Edge Cases

What should the algorithm do immediately after the window becomes valid?

Complexity and Final Recipe

Learning goal: Explain why the frequency-map solution meets the target complexity.

Core idea Although there is a nested-looking while loop, the algorithm is linear because left and right each move only forward. Every character enters the window once and leaves it at most once. The maps hold counts for the character alphabet, so auxiliary space depends on the alphabet rather than the input length.

Algorithm plan

Build need in O(|t|) time.
Scan s with right and maintain missing.
Contract with left while valid.
Return the shortest recorded range.

Micro-example For ADOBECODEBANC, the right pointer visits 13 positions. The left pointer also advances only forward, so contraction does not restart the scan.

Pitfalls

Calling the method O(n²) merely because one loop is nested inside another.
Forgetting that building the requirement map costs O(|t|).
Claiming O(1) space without stating that the alphabet is bounded.

Recap

Time: O(|s| + |t|), commonly written O(n).
Space: O(alphabet), or O(|s| + |t|) for an unrestricted character set.
The central recipe is: expand, validate, contract, record.

Complexity and Final Recipe

Shows the linear work and alphabet-bounded auxiliary storage.

Complexity analysis

Time

O(n)

Space

O(alphabet)

Where the time goes

Build `need` from tEach required character is counted once.dominantO(n)
Expand with `right`Each source character enters the window once.dominantO(n)
Contract with `left`Each source character leaves the window at most once.dominantO(n)
Store frequency mapsO(alphabet) is constant for a fixed alphabet.O(1)

How it grows

Roughly what that costs

n	10	100	1,000	10,000
O(n)	10	100	1K	10K

Both pointers advance monotonically, so the complete scan is linear while frequency storage stays bounded by the alphabet.

Now try it on your own problem

Paste any LeetCode problem — or one of your own — and codebrew builds a walkthrough like this one for it.

Build a lesson from any problem

Approach

Problem

Examples

Problem and Goal

Algorithm plan

Expand, Then Contract

Algorithm plan

Counting Requirements in O(1) Updates

Algorithm plan

End-to-End Walkthrough

Algorithm plan

Traces the concrete example from first satisfaction through final contraction.

Pitfalls and Edge Cases

Algorithm plan

Complexity and Final Recipe

Algorithm plan

Shows the linear work and alphabet-bounded auxiliary storage.

Related problems