Loading…

hardStringsLC #76Frequently asked

Minimum Window Substring

Q: How do you solve Minimum Window Substring using the Brute Force — Check Every Substring approach?

When to use it: Say it first to anchor the baseline and to make the coverage check explicit. Precompute `need`, a count of each character in `t`. Then for every start `i` and end `j`, count the characters in `s[i..j]` and check it contains at least `need[c]` of every required `c`. Among all substrings that pass, keep the shortest. **Why this is the natural first attempt.** It encodes the definition literally and forces you to define 'covers t' precisely: every required character appears with at least its required multiplicity. That coverage predicate is reused in the optimal solution. **Why we don't ship this.** Enumerating all substrings and rechecking coverage from scratch is wildly redundant — adjacent windows share almost all their characters. With `m` up to `10⁵`, the quadratic (times alphabet) cost is far too slow. The optimal keeps a running window count and an O(1) coverage check, so it never recounts. Time complexity: O(m² · Σ). Space complexity: O(Σ).

LCPractice

Sliding Window · 4 of 6 · 12 min

Given two strings s and t of lengths m and n, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The test cases are generated such that the answer is unique.

In plain English

We need the shortest contiguous slice of s that contains at least as many of each character as t requires. Multiplicity matters: covering t = "aabc" requires two a's, one b, one c. Characters not in t may also appear in the window — that's fine, we just want the smallest window that covers t.

Examples

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Note: "BANC" is the shortest substring containing A, B, and C.

Example 2

Input: s = "a", t = "a"
Output: "a"
Note: The whole string is the minimal window.

Example 3

Input: s = "a", t = "aa"
Output: ""
Note: Only one 'a' available but two needed — no valid window, return "".

Constraints

m == s.length
n == t.length
1 ≤ m, n ≤ 10⁵
s and t consist of uppercase and lowercase English letters

Clarifying questions4First question: Does multiplicity matter?Explore questions

Q1.Does multiplicity matter?
Yes. If t has two 'a's, the window must contain at least two 'a's.
Q2.Can the window contain extra characters not in t?
Yes — extras are allowed; we only require that t is fully covered.
Q3.What if no window covers t?
Return the empty string "".
Q4.Is the answer guaranteed unique?
Yes, the problem guarantees a unique minimal window, so we just track the smallest length.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the smallest window in s that contains all characters of t (with multiplicity). The interview-grade answer is a grow-then-shrink sliding window: expand right until the window covers t, then shrink left as far as possible while it still covers t, recording the smallest valid window. Track coverage with a need-count map and a have/need formed counter. O(|s| + |t|) time, O(Σ) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can run a two-phase (grow then shrink) sliding window with character multiplicity, using a have/need formed counter to check coverage in O(1) instead of comparing maps.

Where candidates slip

Comparing the whole window map to the need map each step (O(Σ) per step), mishandling multiplicity, or incrementing `have` every time a needed char appears instead of only when its count first meets the requirement.

How to stand out

State the brute force, then describe the grow-then-shrink window and the formed counter. Emphasize multiplicity ('aab' needs two a's) and that `have` ticks up only when a count exactly reaches the requirement.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Check Every Substring	`O(m² · Σ)`	`O(Σ)`	Say it first to anchor the baseline and to make the coverage check explicit.	Read
2	Grow-Then-Shrink Window + Formed Counter (Optimal)Optimal	`O(m + n)`	`O(Σ)`	The answer they want. Phrase it as 'expand right until the window covers t, then shrink left while it still covers t, tracking the minimum'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewSmallest window in s covering all of tTrack coverage incrementally?No (recheck all)Yes (have/need)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Check Every Substring

TimeO(m² · Σ)SpaceO(Σ)

Say it first to anchor the baseline and to make the coverage check explicit.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some substring of s. How do you check whether one substring covers all of t with multiplicity?

2Hint 2Explore hint

Build a need-count map of t. For a candidate substring, count its characters and verify each need is met.

3Hint 3Explore hint

Enumerate all O(m²) substrings, test coverage, and keep the shortest that passes. Correct but slow — the coverage recheck is the waste.

A · Core idea

Precompute need, a count of each character in t. Then for every start i and end j, count the characters in s[i..j] and check it contains at least need[c] of every required c. Among all substrings that pass, keep the shortest.

Why this is the natural first attempt. It encodes the definition literally and forces you to define 'covers t' precisely: every required character appears with at least its required multiplicity. That coverage predicate is reused in the optimal solution.

Why we don't ship this. Enumerating all substrings and rechecking coverage from scratch is wildly redundant — adjacent windows share almost all their characters. With m up to 10⁵, the quadratic (times alphabet) cost is far too slow. The optimal keeps a running window count and an O(1) coverage check, so it never recounts.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "ADOBEC", t = "ABC"

i=0

extend until "ADOBEC" covers A,B,C

Statevalid len 6

Final result"ADOBEC"

C · Code with teaching comments

Reference implementation previewpublic String minWindow(String s, String t) { if (s.length() < t.length()) return ""; Map<Character, Integer> need = new HashMap<>(); for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum); int bestLen = Integer.MAX_VALUE, bestStart = -1;Explore the full code

solution.javaJava

Brute Force — Check Every Substring — reference

3 teaching notes

1
public String minWindow(String s, String t) {
2
    if (s.length() < t.length()) return "";
3
    Map<Character, Integer> need = new HashMap<>();
4
    // Required count per character, honoring multiplicity.
5
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
6
    int bestLen = Integer.MAX_VALUE, bestStart = -1;
7
    for (int i = 0; i < s.length(); i++) {
8
        Map<Character, Integer> have = new HashMap<>();
9
        for (int j = i; j < s.length(); j++) {
10
            have.merge(s.charAt(j), 1, Integer::sum);
11
            // Coverage predicate plus a shorter-than-best check.
12
            if (covers(have, need) && j - i + 1 < bestLen) {
13
                bestLen = j - i + 1;
14
                bestStart = i;
15
                break;
16
            }
17
        }
18
    }
19
    return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
20
}
21
 
22
private boolean covers(Map<Character, Integer> have, Map<Character, Integer> need) {
23
    for (Map.Entry<Character, Integer> e : need.entrySet()) {
24
        // Every required char must meet its required multiplicity.
25
        if (have.getOrDefault(e.getKey(), 0) < e.getValue()) return false;
26
    }
27
    return true;
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(m² · Σ) timeO(Σ) spaceOpen the invariant and proofExplore the proof

Every adjacent substring differs by only one character on each end, yet the brute force recounts the entire window. Maintaining incremental counts plus a 'how many requirements are currently met' counter removes all the recounting.

ComplexityO(m² · Σ) time, O(Σ) space — O(m²) substrings; each coverage check compares counts over the alphabet, O(Σ) (or O(window) to count). Total O(m²·Σ). The count maps are O(Σ) space.

E · Edge cases and pitfalls3Ignoring multiplicity — treating t as a set so "aa" passes with a single 'a'.Explore edge cases

Pitfalls

Ignoring multiplicity — treating t as a set so "aa" passes with a single 'a'.
Rechecking full coverage every step (O(Σ)) instead of tracking it incrementally.
Forgetting the m < n early exit and the empty-string fallback.

03.2

Approach 2 of 2 · Optimal

Grow-Then-Shrink Window + Formed Counter (Optimal)

TimeO(m + n)SpaceO(Σ)

The answer they want. Phrase it as 'expand right until the window covers t, then shrink left while it still covers t, tracking the minimum'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build need = counts of t and required = number of distinct chars in t. Keep a window count map and a counter `have` of how many distinct requirements are currently fully met.

2Hint 2Explore hint

Expand right: add s[right] to the window; if that char's window count just reached its need, increment have.

3Hint 3Explore hint

While have == required (window is valid), record the window if it's the smallest, then shrink from the left: remove s[left], and if that drops a needed char below its requirement, decrement have. Advance left.

A · Core idea

Precompute need (the count of each character in t) and required (the number of distinct characters in t). Maintain a window count map and an integer have = how many distinct required characters are currently satisfied at full multiplicity. The window is valid exactly when have == required.

Phase 1 — grow to feasibility. Move right across s, incrementing window[c]. The instant a required character's window count reaches its needed count (window[c] == need[c]), one more requirement is met, so have += 1. We only bump have on the exact match — counting beyond the requirement doesn't satisfy a new requirement, so it must not increment have again.

Phase 2 — shrink to minimality. Once have == required, the window covers t. But it may be padded with junk on the left. So while it stays valid, record it if it's the smallest seen, then try to shrink: decrement window[s[left]] and advance left. If removing that character drops a needed character below its requirement (window[c] < need[c]), the window is no longer valid, so have -= 1 and the shrink loop stops. This finds the tightest window ending at the current right.

Why the formed counter beats comparing maps. Naively you'd compare the whole window map to need at each step — O(Σ) per step. The have/required counter compresses 'is the window valid?' into a single integer comparison, updated in O(1) as characters enter and leave. That's what turns the brute force's O(m²·Σ) into O(m + n).

Why multiplicity is handled correctly. Because have increments only when a count reaches need[c] and decrements only when it falls below need[c], a character that needs two copies contributes to have only while both copies are present. The window can't be declared valid with too few copies.

Why O(m + n) time. Each pointer sweeps s once; building need is O(n). Every character enters the window once (via right) and leaves at most once (via left).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "ADOBECODEBANC", t = "ABC"

Array state

r=5

"ADOBEC" covers A,B,C (have=3)

l ↓

[0]

[1]

[2]

[3]

[4]

r ↓

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Current pointerResolved stateNot processed

Final result"BANC"

C · Code with teaching comments

solution.javaJava

Grow-Then-Shrink Window + Formed Counter (Optimal) — optimal

4 teaching notes

1
public String minWindow(String s, String t) {
2
    if (s.length() < t.length()) return "";
3
    Map<Character, Integer> need = new HashMap<>();
4
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
5
    // Number of distinct characters that must be fully satisfied.
6
    int required = need.size();
7
    Map<Character, Integer> window = new HashMap<>();
8
    int have = 0;
9
    int bestLen = Integer.MAX_VALUE, bestStart = 0;
10
    int left = 0;
11
    for (int right = 0; right < s.length(); right++) {
12
        char c = s.charAt(right);
13
        window.merge(c, 1, Integer::sum);
14
        // Bump have only when a needed char's count exactly meets its requirement.
15
        if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
16
            have++;
17
        }
18
        // Window is valid — try to shrink it from the left.
19
        while (have == required) {
20
            if (right - left + 1 < bestLen) {
21
                bestLen = right - left + 1;
22
                bestStart = left;
23
            }
24
            char lc = s.charAt(left);
25
            window.merge(lc, -1, Integer::sum);
26
            // Removing this char broke coverage → decrement have and stop shrinking.
27
            if (need.containsKey(lc) && window.get(lc) < need.get(lc)) {
28
                have--;
29
            }
30
            left++;
31
        }
32
    }
33
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(m + n) timeO(Σ) spaceOpen the invariant and proofExplore the proof

The two-phase rhythm — grow until feasible, then shrink while still feasible — is the universal minimum-window template. The reusable optimization is the have == required counter: rather than re-verifying the whole constraint, track how close you are to satisfying it and adjust by ±1 as elements cross the window boundary.

ComplexityO(m + n) time, O(Σ) space — `right` advances m times and `left` advances at most m times, each doing O(1) map work → O(m) for the scan plus O(n) to build need = O(m + n) time. The maps hold at most Σ distinct characters → O(Σ) space.

E · Edge cases and pitfalls6s = "a", t = "aa" — need{a:2}; window never reaches 2 a's, have stays 0, best never set → returns "".Explore edge cases

Edge cases handled

s = "a", t = "aa"need{a:2}; window never reaches 2 a's, have stays 0, best never set → returns "".
s = "ab", t = "b"Window grows to include 'b', shrinks to just "b" (len 1).
s = "aa", t = "aa"Needs two a's; the only valid window is the whole "aa".

Pitfalls

Incrementing have on every needed char instead of only when the count first reaches the requirement.
Comparing have against t.length() instead of the number of distinct required characters.
Decrementing have when a non-required char leaves the window (it should only react to needed chars dropping below requirement).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String minWindow(String s, String t) { if (s.length() < t.length()) return ""; Map<Character, Integer> need = new HashMap<>(); for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum); int required = need.size();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
    int required = need.size();
    Map<Character, Integer> window = new HashMap<>();
    int have = 0;
    int bestLen = Integer.MAX_VALUE, bestStart = 0;
    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.merge(c, 1, Integer::sum);
        if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
            have++;
        }
        while (have == required) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            char lc = s.charAt(left);
            window.merge(lc, -1, Integer::sum);
            if (need.containsKey(lc) && window.get(lc) < need.get(lc)) {
                have--;
            }
            left++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Bumping `have` past the requirement

have must count satisfied distinct requirements. Incrementing it whenever a needed char appears (even beyond need[c]) over-counts and declares invalid windows valid.

Explore the code comparison

Don't write this

if c in need:
    have += 1

Write this instead

if c in need and window[c] == need[c]:
    have += 1

Comparing have to len(t)

required is the number of *distinct* characters in t, not its length. For t = "aab", required is 2, not 3.

Explore the code comparison

Don't write this

while (have == t.length()) {
    // shrink
}

Write this instead

int required = need.size();
while (have == required) {
    // shrink
}

Forgetting the empty-result fallback

If no window ever covers t, bestLen stays at its sentinel; returning a substring then throws or returns garbage.

Explore the code comparison

Don't write this

return s[best_start:best_start + best_len]

Write this instead

return "" if best_len == float('inf') else s[best_start:best_start + best_len]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Grow-then-shrink window with have/need counts

Code pattern to memorize

need = Counter(t); required = len(need)
have = 0; window = {}
best = (inf, 0, 0)
l = 0
for r, c in enumerate(s):
    window[c] += 1
    if c in need and window[c] == need[c]: have += 1
    while have == required:
        if r - l + 1 < best[0]: best = (r-l+1, l, r)
        window[s[l]] -= 1
        if s[l] in need and window[s[l]] < need[s[l]]: have -= 1
        l += 1

Rules to remember

1Match characters with multiplicity — if t = "aab", the window needs two a's.
2have counts how many distinct required characters are fully satisfied; valid when have == required.
3Increment have only when a count reaches exactly need[c] (not above).
4Shrink from the left while the window is valid, recording the minimum, then break validity by dropping a needed char.
5Return "" when no valid window exists (best length never updated).

Use this pattern when

Smallest contiguous window that covers a required multiset of items
Coverage can be tracked incrementally with a need map and a satisfied counter
Grow to become feasible, then shrink to minimize — a two-phase window
Substring/subarray 'contains all of X' minimization problems

Choose another pattern when

Order of t matters / t must appear contiguously → that's substring search (KMP)
Longest valid window, not shortest → grow-only window (LC3, LC424)
Fixed-size window → simpler fixed sliding window (Permutation in String)

Interview takeaway

Grow-then-shrink is the template for minimum-window problems: expand the right edge until the constraint is met, then contract the left edge while it stays met. The have/need formed counter turns 'does the window cover t?' into an O(1) check per step.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternGrow-then-shrink sliding window with a have/required formed counter. Reach for it on 'smallest window covering a required multiset' problems. Same family as Permutation in String and Find All Anagrams.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Permutation in String
Fixed-size window covering exactly t's multiset — no shrink phase needed.
Find All Anagrams in a String
Coming soon
Same fixed window as Permutation in String, but collect every matching start index.
Longest Substring Without Repeating Characters
Grow-only window — the longest-instead-of-shortest variable window.
Minimum Window Subsequence
Coming soon
t must appear in order as a subsequence — needs a two-pointer / DP twist, not just counts.

Same pattern

←

Longest Repeating Character Replacement

Continue · Next problem

Permutation in String

hardStringsLC #76Frequently asked

Minimum Window Substring

LCPractice

Sliding Window · 4 of 6 · 12 min

The test cases are generated such that the answer is unique.

In plain English

Examples

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Note: "BANC" is the shortest substring containing A, B, and C.

Example 2

Input: s = "a", t = "a"
Output: "a"
Note: The whole string is the minimal window.

Example 3

Input: s = "a", t = "aa"
Output: ""
Note: Only one 'a' available but two needed — no valid window, return "".

Constraints

m == s.length
n == t.length
1 ≤ m, n ≤ 10⁵
s and t consist of uppercase and lowercase English letters

Clarifying questions4First question: Does multiplicity matter?Explore questions

Q1.Does multiplicity matter?
Yes. If t has two 'a's, the window must contain at least two 'a's.
Q2.Can the window contain extra characters not in t?
Yes — extras are allowed; we only require that t is fully covered.
Q3.What if no window covers t?
Return the empty string "".
Q4.Is the answer guaranteed unique?
Yes, the problem guarantees a unique minimal window, so we just track the smallest length.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can run a two-phase (grow then shrink) sliding window with character multiplicity, using a have/need formed counter to check coverage in O(1) instead of comparing maps.

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Check Every Substring	`O(m² · Σ)`	`O(Σ)`	Say it first to anchor the baseline and to make the coverage check explicit.	Read
2	Grow-Then-Shrink Window + Formed Counter (Optimal)Optimal	`O(m + n)`	`O(Σ)`	The answer they want. Phrase it as 'expand right until the window covers t, then shrink left while it still covers t, tracking the minimum'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Check Every Substring

TimeO(m² · Σ)SpaceO(Σ)

Say it first to anchor the baseline and to make the coverage check explicit.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some substring of s. How do you check whether one substring covers all of t with multiplicity?

2Hint 2Explore hint

Build a need-count map of t. For a candidate substring, count its characters and verify each need is met.

3Hint 3Explore hint

Enumerate all O(m²) substrings, test coverage, and keep the shortest that passes. Correct but slow — the coverage recheck is the waste.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "ADOBEC", t = "ABC"

i=0

extend until "ADOBEC" covers A,B,C

Statevalid len 6

Final result"ADOBEC"

C · Code with teaching comments

solution.javaJava

Brute Force — Check Every Substring — reference

3 teaching notes

1
public String minWindow(String s, String t) {
2
    if (s.length() < t.length()) return "";
3
    Map<Character, Integer> need = new HashMap<>();
4
    // Required count per character, honoring multiplicity.
5
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
6
    int bestLen = Integer.MAX_VALUE, bestStart = -1;
7
    for (int i = 0; i < s.length(); i++) {
8
        Map<Character, Integer> have = new HashMap<>();
9
        for (int j = i; j < s.length(); j++) {
10
            have.merge(s.charAt(j), 1, Integer::sum);
11
            // Coverage predicate plus a shorter-than-best check.
12
            if (covers(have, need) && j - i + 1 < bestLen) {
13
                bestLen = j - i + 1;
14
                bestStart = i;
15
                break;
16
            }
17
        }
18
    }
19
    return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
20
}
21
 
22
private boolean covers(Map<Character, Integer> have, Map<Character, Integer> need) {
23
    for (Map.Entry<Character, Integer> e : need.entrySet()) {
24
        // Every required char must meet its required multiplicity.
25
        if (have.getOrDefault(e.getKey(), 0) < e.getValue()) return false;
26
    }
27
    return true;
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(m² · Σ) timeO(Σ) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Ignoring multiplicity — treating t as a set so "aa" passes with a single 'a'.Explore edge cases

Pitfalls

Ignoring multiplicity — treating t as a set so "aa" passes with a single 'a'.
Rechecking full coverage every step (O(Σ)) instead of tracking it incrementally.
Forgetting the m < n early exit and the empty-string fallback.

03.2

Approach 2 of 2 · Optimal

Grow-Then-Shrink Window + Formed Counter (Optimal)

TimeO(m + n)SpaceO(Σ)

The answer they want. Phrase it as 'expand right until the window covers t, then shrink left while it still covers t, tracking the minimum'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build need = counts of t and required = number of distinct chars in t. Keep a window count map and a counter `have` of how many distinct requirements are currently fully met.

2Hint 2Explore hint

Expand right: add s[right] to the window; if that char's window count just reached its need, increment have.

3Hint 3Explore hint

A · Core idea

Why O(m + n) time. Each pointer sweeps s once; building need is O(n). Every character enters the window once (via right) and leaves at most once (via left).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "ADOBECODEBANC", t = "ABC"

Array state

r=5

"ADOBEC" covers A,B,C (have=3)

l ↓

[0]

[1]

[2]

[3]

[4]

r ↓

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Current pointerResolved stateNot processed

Final result"BANC"

C · Code with teaching comments

solution.javaJava

Grow-Then-Shrink Window + Formed Counter (Optimal) — optimal

4 teaching notes

1
public String minWindow(String s, String t) {
2
    if (s.length() < t.length()) return "";
3
    Map<Character, Integer> need = new HashMap<>();
4
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
5
    // Number of distinct characters that must be fully satisfied.
6
    int required = need.size();
7
    Map<Character, Integer> window = new HashMap<>();
8
    int have = 0;
9
    int bestLen = Integer.MAX_VALUE, bestStart = 0;
10
    int left = 0;
11
    for (int right = 0; right < s.length(); right++) {
12
        char c = s.charAt(right);
13
        window.merge(c, 1, Integer::sum);
14
        // Bump have only when a needed char's count exactly meets its requirement.
15
        if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
16
            have++;
17
        }
18
        // Window is valid — try to shrink it from the left.
19
        while (have == required) {
20
            if (right - left + 1 < bestLen) {
21
                bestLen = right - left + 1;
22
                bestStart = left;
23
            }
24
            char lc = s.charAt(left);
25
            window.merge(lc, -1, Integer::sum);
26
            // Removing this char broke coverage → decrement have and stop shrinking.
27
            if (need.containsKey(lc) && window.get(lc) < need.get(lc)) {
28
                have--;
29
            }
30
            left++;
31
        }
32
    }
33
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(m + n) timeO(Σ) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s = "a", t = "aa" — need{a:2}; window never reaches 2 a's, have stays 0, best never set → returns "".Explore edge cases

Edge cases handled

s = "a", t = "aa"need{a:2}; window never reaches 2 a's, have stays 0, best never set → returns "".
s = "ab", t = "b"Window grows to include 'b', shrinks to just "b" (len 1).
s = "aa", t = "aa"Needs two a's; the only valid window is the whole "aa".

Pitfalls

Incrementing have on every needed char instead of only when the count first reaches the requirement.
Comparing have against t.length() instead of the number of distinct required characters.
Decrementing have when a non-required char leaves the window (it should only react to needed chars dropping below requirement).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Bumping `have` past the requirement

have must count satisfied distinct requirements. Incrementing it whenever a needed char appears (even beyond need[c]) over-counts and declares invalid windows valid.

Explore the code comparison

Don't write this

if c in need:
    have += 1

Write this instead

if c in need and window[c] == need[c]:
    have += 1

Comparing have to len(t)

required is the number of *distinct* characters in t, not its length. For t = "aab", required is 2, not 3.

Explore the code comparison

Don't write this

while (have == t.length()) {
    // shrink
}

Write this instead

int required = need.size();
while (have == required) {
    // shrink
}

Forgetting the empty-result fallback

If no window ever covers t, bestLen stays at its sentinel; returning a substring then throws or returns garbage.

Explore the code comparison

Don't write this

return s[best_start:best_start + best_len]

Write this instead

return "" if best_len == float('inf') else s[best_start:best_start + best_len]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Grow-then-shrink window with have/need counts

Code pattern to memorize

need = Counter(t); required = len(need)
have = 0; window = {}
best = (inf, 0, 0)
l = 0
for r, c in enumerate(s):
    window[c] += 1
    if c in need and window[c] == need[c]: have += 1
    while have == required:
        if r - l + 1 < best[0]: best = (r-l+1, l, r)
        window[s[l]] -= 1
        if s[l] in need and window[s[l]] < need[s[l]]: have -= 1
        l += 1

Rules to remember

1Match characters with multiplicity — if t = "aab", the window needs two a's.
2have counts how many distinct required characters are fully satisfied; valid when have == required.
3Increment have only when a count reaches exactly need[c] (not above).
4Shrink from the left while the window is valid, recording the minimum, then break validity by dropping a needed char.
5Return "" when no valid window exists (best length never updated).

Use this pattern when

Smallest contiguous window that covers a required multiset of items
Coverage can be tracked incrementally with a need map and a satisfied counter
Grow to become feasible, then shrink to minimize — a two-phase window
Substring/subarray 'contains all of X' minimization problems

Choose another pattern when

Order of t matters / t must appear contiguously → that's substring search (KMP)
Longest valid window, not shortest → grow-only window (LC3, LC424)
Fixed-size window → simpler fixed sliding window (Permutation in String)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Permutation in String
Fixed-size window covering exactly t's multiset — no shrink phase needed.
Find All Anagrams in a String
Coming soon
Same fixed window as Permutation in String, but collect every matching start index.
Longest Substring Without Repeating Characters
Grow-only window — the longest-instead-of-shortest variable window.
Minimum Window Subsequence
Coming soon
t must appear in order as a subsequence — needs a two-pointer / DP twist, not just counts.

Same pattern

←

Longest Repeating Character Replacement

Continue · Next problem

Permutation in String