Minimum Window Substring

1. Problem & Core Objective

The problem

Given two strings s and t, return the minimum window substring of s such that every character of t — including duplicates — is contained in the window. If there is no such window, return the empty string "".

The answer is guaranteed to be unique.

Input:  s = "ADOBECODEBANC", t = "ABC"      Output: "BANC"
Input:  s = "a", t = "a"                    Output: "a"
Input:  s = "a", t = "aa"                   Output: ""     (only one 'a' available)

Constraints:

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

What the interviewer is actually testing

This is the flagship sliding-window problem and a genuine Hard. Everything in the section builds to it.

1. Do you recognize the shortest-valid template? Expand until valid, then shrink while still valid, recording inside the shrink loop. That placement is the opposite of the longest-valid problems, and getting it backwards is the most common structural failure.
2. Can you make the validity check O(1)? Naively comparing two maps each step is O(k). The have/need counter is the refinement, and the == in its update is subtle.
3. Do you handle duplicates in t? t = "AABC" needs two A's. A Set-based solution silently fails this.
4. Do you avoid the boxed-Integer == trap? Comparing two Integer objects above 127 with == compares references. This is the question where that bites.

2. First-Principles Thought Process

Step 1 — Constraints

m, n up to 10^5.

• O(m² · n) (every substring, checked) → hopeless.
• O(m · n) → 10^10. Too slow.
• O(m + n) → the target.

Uppercase and lowercase — 52 characters. An int[128] over ASCII works; a HashMap is more general. Note this differs from the previous two questions, so check before reaching for int[26].

Step 2 — Restate the requirement precisely

"Contains every character of t, including duplicates" means:

For every distinct character c in t: window.count(c) >= t.count(c).

Two things follow:

• It's a multiset containment, not set containment. t = "AABC" requires two A's.
• The window may be longer than t and contain extra characters — unlike Permutation in String, where the counts must match exactly and the window is therefore fixed-size. That difference — "at least" versus "exactly" — is precisely what makes this a variable-size window.

Step 3 — Which template?

We want the shortest valid window. So:

expand right until the window becomes valid
    then shrink from the left WHILE it stays valid, recording the length each time

Recording happens inside the shrink loop, because each shrink produces a smaller still-valid window — and the smallest one is the last before validity breaks.

Contrast with longest-valid (Q2, Q3), where you shrink while invalid and record after. Same machinery, mirrored.

Step 4 — Make the validity check O(1)

Checking "does the window contain all of t" by comparing two maps is O(k) per step — O(52m) overall. Acceptable, but there's a cleaner way.

Track two numbers:

• required = the number of distinct characters in t. For t = "AABC" that's 3 (A, B, C), not 4.
• have = how many of those distinct characters are currently present in the window in sufficient quantity.

Then the window is valid exactly when have == required — an O(1) test.

Step 5 — The == subtlety in updating have

When a character enters the window:

if (need.containsKey(c) && window.get(c) == need.get(c)) have++;

Why == and not >=? have counts distinct characters that are satisfied. A character transitions from unsatisfied to satisfied exactly once — at the moment its count reaches the required number. If the count then goes from 2 to 3 when only 2 were needed, it was already satisfied, so incrementing again would double-count and inflate have past required.

Symmetrically, on removal you decrement only when the count drops below what's needed:

if (need.containsKey(c) && window.get(c) < need.get(c)) have--;

Step 6 — Why it's O(m + n)

Building need is O(n). Then left and right each traverse s at most once, so the window work is O(m). Every map operation is O(1) average.

3. Solution Paths

Approach 1 — Brute force: check every substring

public String minWindow(String s, String t) {
    String best = "";
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            String sub = s.substring(i, j + 1);
            if (contains(sub, t) && (best.isEmpty() || sub.length() < best.length())) {
                best = sub;
            }
        }
    }
    return best;
}

Where contains checks multiset containment in O(m + n).

• Time: O(m² · (m + n)) — m² substrings, each built and checked.
• Space: O(m) for each substring.

Counter-questions on this approach

⭐ "What do the substrings starting at the same i have in common?"

Each is the previous one plus one character. So the containment check is re-derived from scratch when it could have been updated incrementally in O(1). And substring itself copies in Java, adding a hidden O(m) per iteration on top.

"Once a window starting at i becomes valid, is there any point extending it further?"

None — extending only makes it longer, and we want the shortest. I should break immediately. That observation is already half the sliding window: it tells you the right move after reaching validity is to shrink from the left, not grow from the right.

Approach 2 — Sliding window with map comparison

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);

    Map<Character,Integer> window = new HashMap<>();
    int left = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;

    for (int right = 0; right < s.length(); right++) {
        window.merge(s.charAt(right), 1, Integer::sum);

        while (covers(window, need)) {                     // O(k) check
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            window.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

private boolean covers(Map<Character,Integer> window, Map<Character,Integer> need) {
    for (Map.Entry<Character,Integer> e : need.entrySet()) {
        if (window.getOrDefault(e.getKey(), 0) < e.getValue()) return false;
    }
    return true;
}

• Time: O(m · k) where k is the distinct characters in t — bounded by 52, so O(52m) = O(m).
• Space: O(k).

Counter-questions on this approach

⭐ "You call covers on every shrink iteration. Is that acceptable?"

Asymptotically yes — k is bounded by 52 since the alphabet is fixed, so it's O(52m) = O(m). But it's a real constant factor, and it's avoidable: the validity test can be reduced to comparing two integers with the have/need counters. I'd present this version first for clarity and then refine.

"Why do you record the answer inside the shrink loop rather than after it?"

Because this is a shortest-valid window. Every iteration of the shrink loop produces a smaller window that is still valid, so each one is a candidate and must be measured before shrinking further. Once the loop exits, validity has just broken — measuring there would record an invalid window. Longest-valid problems are the mirror image, recording after the loop.

"Your merge with -1 can leave zero-valued entries in the map. Does that matter?"

Not for correctness — getOrDefault(c, 0) treats a missing key and a zero-valued key identically. It does leave the map slightly larger than necessary. If it mattered I'd use merge(c, -1, (a,b) -> a+b == 0 ? null : a+b), since returning null from merge deletes the entry.

Approach 3 — have/need counters (optimal)

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);

    Map<Character,Integer> window = new HashMap<>();
    int have = 0, required = need.size();          // DISTINCT characters required
    int left = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.merge(c, 1, Integer::sum);

        // did this character just COMPLETE its requirement?
        if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) have++;

        while (have == required) {                 // valid — shrink while it stays valid
            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--;   // broke it
            left++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

Trace on s = "ADOBECODEBANC", t = "ABC" (required = 3):

Answer: "BANC" ✓

• Time: O(m + n).
• Space: O(k) where k ≤ 52.

Counter-questions on this approach

⭐ "Why == and not >= when incrementing have?"

Because have counts distinct characters that are satisfied, not total characters. A character becomes satisfied exactly once — at the moment its window count reaches the required number. If the count later goes from 2 to 3 when only 2 were needed, it was already satisfied, and incrementing again would push have above required, making the while condition unreachable or the window wrongly valid. The == captures the transition, not the state.

⭐ "Why .intValue() on both sides of that comparison?"

Because window.get(c) and need.get(c) both return boxed Integer objects, and == on two Integers compares references, not values. Java caches Integer objects only for −128 to 127, so this would work by accident for small counts and fail silently for counts above 127 — a bug that passes every small test. .intValue() forces primitive comparison. See 03.

"Why is required the number of distinct characters rather than t.length()?"

Because have counts characters that are fully satisfied, one per distinct character. For t = "AABC", required is 3 — A, B, C — and A becomes satisfied when the window holds two of them. Using t.length() would make have == required unreachable.

"On removal you use < rather than ==. Why the asymmetry?"

They're the same transition viewed from opposite directions. On insertion the count rises to exactly need, so == catches the moment of satisfaction. On removal the count falls below need, so < catches the moment it breaks. Writing == on removal would miss the case where the count was above need and dropped straight past it — though with single decrements it can't skip, so == need - 1 would also work. < is clearer and safer.

"What if t contains a character that never appears in s?"

Then have can never reach required, the shrink loop never runs, bestLen stays at Integer.MAX_VALUE, and we return "". No special case needed — the sentinel handles it.

Comparison

4. Why the Optimal Wins

Against brute force. The brute force builds and re-validates m² substrings. The window maintains validity incrementally and never re-examines a character — left and right each cross s once.

Against the map-comparison version. Both are O(m) asymptotically, since the alphabet caps k at 52. The have/need counters reduce the validity test from a loop over k entries to a single integer comparison. It's a constant-factor improvement, and I'd say so rather than overselling it — the value is the technique.

The technique worth naming:

Replace a repeated O(k) predicate with an incrementally-maintained counter, by identifying the exact moment the predicate's truth value can change.

That's the same move as the matches counter in Permutation in String and the running maxFreq in Longest Repeating Character Replacement. Three questions, one idea.

Why O(m + n) is the floor. Both strings must be read: t to know what's required, s because the answer could be anywhere. So O(m + n) is optimal.

5. Java Prerequisites

Counting with merge

need.merge(c, 1, Integer::sum);       // insert 1, or add 1 to the existing value
window.merge(c, -1, Integer::sum);    // decrement

Reads as: "if the key is absent store this value; if present, combine old and new with this function." See 02 §1.3.

To delete on reaching zero:

window.merge(c, -1, (a, b) -> a + b == 0 ? null : a + b);

Returning null from merge removes the entry.

The boxed Integer == trap

Integer a = 1000, b = 1000;
a == b;                 // false — different objects
a.equals(b);            // true
a.intValue() == b.intValue();   // true

Java caches Integer objects for −128 to 127 only. Above that, == compares references.

In this problem, window.get(c) == need.get(c) is a latent bug that works for counts up to 127 and fails silently beyond. Since t can be 10^5 characters, a single character could genuinely need more than 127 occurrences. Use .intValue() on both sides, or .equals().

Note that window.get(lc) < need.get(lc) is safe — relational operators auto-unbox and compare numerically. Only == and != have the reference problem.

Map.size() for distinct count

int required = need.size();     // DISTINCT characters, not total

Sentinel for "no answer found"

int bestLen = Integer.MAX_VALUE;
...
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);

Using MAX_VALUE rather than -1 lets the < comparison work without a special first case. The final check distinguishes "never found" from a real answer.

Recording start plus length, not the substring

bestStart = left;  bestLen = right - left + 1;

Storing indices and materializing the substring once at the end avoids an O(m) copy on every improvement. substring copies in Java 7+.

6. Interview Communication Guide

Clarifying questions

1. "Does the window need every character of t including duplicates?" — yes, multiset containment. t = "AABC" needs two A's. This is the question that decides Map versus Set.
2. "Can the window contain extra characters not in t?" — yes, which is what makes it variable-size rather than fixed.
3. "What do I return if no valid window exists?" — the empty string.
4. "Is the answer guaranteed unique?" — the problem says yes, so I don't need tie-breaking rules.
5. "What's the character set — lowercase only?" — uppercase and lowercase here, so 52. Worth asking rather than assuming int[26].

The pitch

"I need the shortest substring of s containing all of t's characters, including duplicates.

Brute force checks every substring — O(m²) of them, each validated — far too slow.

The structure is a sliding window, and specifically the shortest-valid shape: expand right until the window becomes valid, then shrink from the left while it's still valid, recording the length at each shrink. That's the opposite of the longest-valid problems, where you shrink while invalid and record afterwards.

The naive validity check compares two count maps, which is O(k) per step. I can make it O(1) with two counters: required is the number of distinct characters t needs, and have is how many of those are currently present in sufficient quantity. The window is valid exactly when have == required.

The subtle part is updating have. I increment only when a character's count reaches exactly what's needed — using ==, not >= — because have counts satisfied characters, and going from 2 to 3 when 2 were required doesn't satisfy anything new.

One Java detail: both counts come back as boxed Integers, and == on those compares references above 127. I'll use .intValue() on both sides.

O(m + n) time, O(k) space."

Edge cases to raise proactively

s = "a", t = "aa" is the one to volunteer. It's the case that breaks any solution using a Set or ignoring multiplicity — such a solution sees a present and returns "a". Naming it proves you read "including duplicates".

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "What if the alphabet were Unicode rather than English letters?"

The HashMap version already handles it unchanged — that's why I'd choose maps over int[52] if generality mattered. Space becomes O(k) in the distinct characters of t. The one subtlety is that Java char is 16 bits, so characters outside the Basic Multilingual Plane occupy two chars; iterating codePoints() fixes that.

"What if you needed the longest window containing all of t, rather than the shortest?"

Trivially the whole string if any valid window exists, since supersets of a valid window remain valid — that's the monotonicity. The question only makes sense in the shortest direction, which is worth pointing out rather than attempting.

"What if you had to return all minimal windows, not just one?"

Collect every window whose length equals the eventual minimum. Since you don't know the minimum until the end, either do two passes, or keep a list and clear it whenever a strictly shorter window is found. Still O(m + n) time.

"What if t could contain characters with a maximum count as well as a minimum — at least 2 A's but at most 3?"

Validity is no longer monotonic in window size: growing the window can violate an upper bound, so a larger window isn't automatically still valid. That breaks the shrink-while-valid logic. You'd need to track violations in both directions and handle the window becoming invalid from either end — considerably harder, and worth flagging as a structural break rather than guessing.

"What if s streams in and can't be indexed backwards?"

Buffer the current window in a Deque<Character> so the departing character can be evicted without indexing s. Memory becomes O(window size) rather than O(1) beyond the maps — acceptable, since you'd also need to retain the best window's contents to return it.

"What if you had many queries t₁, t₂, … against the same s?"

Each query is an independent O(m + n) pass, so O(q · m) overall. Precomputation doesn't obviously help, because the answer depends on the whole multiset of the query. If all queries were short and over a small alphabet you could precompute prefix counts per character — O(52m) once — and then test containment for a candidate window in O(52), but you'd still need to search over windows.