Minimum Window Substring

HardSliding Window · Dynamic Size🧩 Sliding Window LeetCode #76 ↗Updated Oct 30, 2026

Problem

Given strings s and t, find the shortest contiguous substring of s that contains every character of t, counting duplicates (if t has two 'a's, the window needs two). Return "" if no such window exists; the answer is guaranteed unique.

Inputs="ADOBECODEBANC", t="ABC"Output"BANC"

Inputs="a", t="a"Output"a"

Inputs="a", t="aa"Output""

1 ≤ m, n ≤ 10⁵ · upper/lower-case English letters · Follow-up: O(m + n) time.

Try it yourself

Java

class Solution {
    public String minWindow(String s, String t) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Expand right until the window is valid, then shrink left while it stays valid. A single counter missing (chars of t still uncovered) makes the validity test O(1).

PatternSliding Window

Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.

Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.

Open the Sliding Window guide →

Approaches

Brute ForceCheck Every Substring

Time O(n³ + m)Space O(1)

Count t once into need[128]. For every pair (i, j), recount s[i..j] and compare all 128 slots. Keep the shortest window that covers need.

Java

public String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int bestLen = Integer.MAX_VALUE, bestStart = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            if (j - i + 1 < bestLen && covers(s, i, j, need)) {
                bestLen = j - i + 1;
                bestStart = i;
            }
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

private boolean covers(String s, int i, int j, int[] need) {
    int[] have = new int[128];
    for (int k = i; k <= j; k++) have[s.charAt(k)]++;
    for (int c = 0; c < 128; c++) if (have[c] < need[c]) return false;
    return true;
}

Correct and simple, but recounting each of O(n²) windows is far too slow.

BetterFix Start, Grow End Incrementally

Time O(n² + m)Space O(1)

For each start i, extend j while updating a copy of need and a missing counter. The first j where missing == 0 is the shortest window from i, so break.

Java

public String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int bestLen = Integer.MAX_VALUE, bestStart = 0;
    for (int i = 0; i < s.length(); i++) {
        int[] left = need.clone();
        int missing = t.length();
        for (int j = i; j < s.length() && j - i + 1 < bestLen; j++) {
            if (left[s.charAt(j)]-- > 0) missing--;
            if (missing == 0) { bestLen = j - i + 1; bestStart = i; break; }
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

Drops a factor of n, but every start still rescans the string.

OptimalSliding Window + Missing Counter

Time O(n + m)Space O(1)

need[c] = how many more c the window needs (negative = surplus). Adding c with need[c] > 0 lowers missing. While missing == 0, record the window and drop s[left]; if that makes need positive, the window breaks. Each pointer moves at most n times.

Java

public String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int missing = t.length(), left = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;
    for (int right = 0; right < s.length(); right++) {
        if (need[s.charAt(right)]-- > 0) missing--; // a still-needed char
        while (missing == 0) {                      // valid: try to shrink
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            if (++need[s.charAt(left++)] > 0) missing++; // dropped a needed char
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

Dry runs="ADBECBA", t="ABC"

l leftr right changed

r=2
A
l
D

B
r
E

C

B

A

A,B covered, missing=1
r=4
A
l
D

B

E

C
r
B

A

missing=0 → best=5
l=1
A

D
l
B

E

C
r
B

A

drop A → missing=1
r=6
A

D
l
B

E

C

B

A
r
A again → valid (len 6)
l=4
A

D

B

E

C
l
B

A
r
drop D,B,E → best=3
l=5
A

D

B

E

C

B
l
A
r
drop C → "CBA" ✔

Linear, fixed 128-int table — meets the follow-up.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Substring	`O(n³ + m)`	`O(1)`
Better	Fix Start, Grow End Incrementally	`O(n² + m)`	`O(1)`
Optimal	Sliding Window + Missing Counter	`O(n + m)`	`O(1)`

Common pitfalls

Tracking distinct chars only — t = "aa" needs two as.
Calling substring on every improvement — store start/length instead.
Comparing boxed Integers with == in a HashMap version (fails above 127).

Interview tips

Describe the template: expand until valid, shrink while valid.
Explain the O(1) validity check via missing instead of comparing maps.
Mention the “filtered s” trick when t is tiny and s huge.

Pattern

Shrinkable sliding window → shortest substring/subarray that satisfies a coverage (count) condition.

My notes saved in this browser