#76 Minimum Window Substring

frequently reported atAdobe ByteDance / TikTok Meta LinkedIn Airbnb Amazon

the problem

In plain words

Return the shortest substring of s that contains every character of t, including duplicates. Return "" if there is none.

in s = "ADOBECODEBANC", t = "ABC"

out "BANC"

in s = "a", t = "a"

out "a"

The whole string is the window.

in s = "a", t = "aa"

out ""

t needs two a's; s has one.

1 ≤ s.length, t.length ≤ 10⁵
Upper- and lowercase English letters
The answer is unique

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternSliding window (variable size)Frequency counting

Expand right until the window covers t. Then shrink left as long as it still covers t — every step of that shrink is a candidate answer. A single missing counter tells you coverage in O(1).

solutions

From brute force to optimal

For each start, extend until the window covers t; keep the shortest.

need = counts of t.
For each i: extend j, updating have, until have ⊇ need (check all 128 chars).
Keep the shortest window found.

timeO(|s|² · σ)

|s|² (i, j) pairs, each with a σ = 128 coverage check.

spaceO(σ)

Two count arrays.

java

1class Solution {2    public String minWindow(String s, String t) {3        int[] need = new int[128];4        for (char c : t.toCharArray()) need[c]++;5        String best = "";6        for (int i = 0; i < s.length(); i++) {7            int[] have = new int[128];8            for (int j = i; j < s.length(); j++) {9                have[s.charAt(j)]++;10                if (covers(have, need)) {             // shortest window starting at i11                    if (best.isEmpty() || j - i + 1 < best.length()) best = s.substring(i, j + 1);12                    break;13                }14            }15        }16        return best;17    }18 19    private boolean covers(int[] have, int[] need) {20        for (int c = 0; c < 128; c++) if (have[c] < need[c]) return false;21        return true;22    }23}

need[c] = how many more of c we need (negative = spare). missing = total chars still needed.

need = counts of t; missing = |t|.
Add s[right]: if need[c] > 0 before decrementing, missing--.
While missing == 0: record the window; remove s[left] (need[c]++); if need[c] > 0, missing++; left++.

timeO(|s| + |t|)

Counting t once, then each index of s enters and leaves at most once.

spaceO(σ) = O(1)

A 128-slot array.

java

1class Solution {2    public String minWindow(String s, String t) {3        int[] need = new int[128];4        for (char c : t.toCharArray()) need[c]++;5        int missing = t.length();           // chars of t not yet covered6        int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;7        for (int right = 0; right < s.length(); right++) {8            if (need[s.charAt(right)]-- > 0) missing--; // a still-needed char arrived9            while (missing == 0) {          // window covers t: try to shrink10                if (right - left + 1 < bestLen) {11                    bestLen = right - left + 1;12                    bestStart = left;13                }14                if (++need[s.charAt(left)] > 0) missing++; // we just lost a needed char15                left++;16            }17        }18        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);19    }20}

sim

Dry run

loading simulation…

java

1class Solution {2    public String minWindow(String s, String t) {3        int[] need = new int[128];4        for (char c : t.toCharArray()) need[c]++;5        int missing = t.length();           // chars of t not yet covered6        int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;7        for (int right = 0; right < s.length(); right++) {8            if (need[s.charAt(right)]-- > 0) missing--; // a still-needed char arrived9            while (missing == 0) {          // window covers t: try to shrink10                if (right - left + 1 < bestLen) {11                    bestLen = right - left + 1;12                    bestStart = left;13                }14                if (++need[s.charAt(left)] > 0) missing++; // we just lost a needed char15                left++;16            }17        }18        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);19    }20}

in the room

How to say it in the interview

talk track

Explain need/missing before coding: "need can go negative — that means spare copies, which are safe to drop".
This is the shortest pattern: the answer is recorded inside the shrink loop.
Store bestStart and bestLen, and build the substring once at the end — not on every improvement.

traps

Counting distinct characters instead of total characters — t = "aa" needs two a's.
Calling substring inside the loop on every improvement: extra O(n) copies per update.

what they ask next

Follow-ups

Minimum Window Subsequence (LC 727): t must appear in order?

Different problem — a forward scan to find t, then a backward scan to tighten the start; or DP.

before you submit

Edge cases to test

t longer than s, or a letter of t missing from s → "".
Duplicates in t: "aa" needs two a's in the window.
Case matters: 'A' and 'a' are different characters.
t is a single character → that character alone is the window.

practise next