19.Minimum Window Substring

HardBlind 75Sliding Window · 5/6

Problem

Given strings s and t, return the shortest substring of s that contains every character of t, including duplicates. If no such substring exists, return the empty string "".

The test data guarantees the answer is unique.

Examples

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" contains 'A', 'B' and 'C' and no shorter window does.

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

Input:  s = "a", t = "aa"
Output: ""
Explanation: t needs two 'a's but s has only one.

Constraints

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

💡 Key Insight

Use a variable-size 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. To test "covers t" in O(1), keep a single counter missing = how many characters of t (with multiplicity) the window still lacks; it only changes when a needed character enters or leaves.

Brute Force

TimeO(m² · 128)SpaceO(1)

Intuition

Check every substring s[i..j]: count its characters and test whether each character of t appears at least as many times. Keep the shortest one that passes. Extending j incrementally avoids recounting from scratch.

Algorithm

Build need[128] from t.
For each start i: reset have[128]; for each end j >= i, add s[j] to have.
If have[c] >= need[c] for every c, record s[i..j] if shorter than the best, then break (longer windows from i cannot be shorter).
Return the best window or "".

Visualization

s = "ADOBECODEBANC", t = "ABC"

i=0: A D O B E C        covers at j=5 → "ADOBEC" (6)
i=1: D O B E C O D E B A covers at j=10 → length 10
...
i=9: B A N C            covers at j=12 → "BANC" (4) ✓ shortest

Code

java

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray()) {
            need[c]++;
        }
        int bestStart = 0, bestLen = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            int[] have = new int[128];
            for (int j = i; j < s.length(); j++) {
                have[s.charAt(j)]++;
                if (covers(have, need)) {
                    if (j - i + 1 < bestLen) {
                        bestLen = j - i + 1;
                        bestStart = i;
                    }
                    break; // extending j further only makes it longer
                }
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }

    private boolean covers(int[] have, int[] need) {
        for (int c = 0; c < 128; c++) {
            if (have[c] < need[c]) {
                return false;
            }
        }
        return true;
    }
}

Complexity

Time: O(m² · 128) — O(m²) windows, each checked against 128 counters.
Space: O(1) — fixed-size count arrays.

Sliding Window + Full Coverage Check

TimeO(128 · m)SpaceO(1)

Intuition

If s[left..right] covers t, then any window that starts at left and ends later also covers it — so once covered we should try moving left forward instead. Use two pointers: grow right, and while the window covers t, record it and shrink from the left. Coverage is still tested by scanning all 128 counters.

Algorithm

Build need; left = 0, have[128].
For each right: add s[right] to have.
While covers(have, need): record the window if shorter; remove s[left] from have; left++.
Return the best window or "".

Dry Run

s = "ADOBECODEBANC", t = "ABC"

right=5  "ADOBEC" covers → record 6, shrink: drop A → no longer covers
right=10 "DOBECODEBA" covers → shrink to "CODEBA" (6), then drop C → stop
right=12 "ODEBANC" covers → shrink to "BANC" (4) ✓, drop B → stop
answer = "BANC"

Code

java

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray()) {
            need[c]++;
        }
        int[] have = new int[128];
        int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            have[s.charAt(right)]++;
            // shrink while the window still contains all of t
            while (covers(have, need)) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestStart = left;
                }
                have[s.charAt(left)]--;
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }

    private boolean covers(int[] have, int[] need) {
        for (int c = 0; c < 128; c++) {
            if (have[c] < need[c]) {
                return false;
            }
        }
        return true;
    }
}

Complexity

Time: O(128 · m) — each pointer moves at most m times, each move followed by a 128-slot check.
Space: O(1) — fixed-size arrays.

Sliding Window + Missing CounterOptimal

TimeO(m + n)SpaceO(1)

Intuition

Replace the 128-slot check with one integer. Let need[c] be how many more copies of c the window still requires (it can go negative for surplus). Let missing = total required characters not yet in the window, starting at t.length().

When s[right] enters and need[c] > 0, it fills a real gap → missing--. Then need[c]--.
When s[left] leaves, need[c]++; if it becomes > 0, we just lost a required character → missing++.

The window covers t exactly when missing == 0.

Algorithm

need[c]++ for each c in t; missing = t.length(); left = 0.
For each right:
- c = s[right]; if need[c] > 0, missing--; need[c]--.
- While missing == 0: record [left, right] if shorter; d = s[left]; need[d]++; if need[d] > 0, missing++; left++.
Return the best window or "".

Dry Run

flowchart TD
    A["s = 'ADOBECODEBANC', t = 'ABC'<br/>missing = 3"] --> B["right = 5: 'ADOBEC'<br/>missing = 0, best = 6"]
    B --> C["drop 'A' → missing = 1<br/>left = 1"]
    C --> D["right = 10: 'DOBECODEBA'<br/>missing = 0"]
    D --> E["shrink past D, O, B, E<br/>('B' surplus, first B leaves freely)<br/>window 'CODEBA', len 6"]
    E --> F["drop 'C' → missing = 1<br/>left = 6"]
    F --> G["right = 12: 'ODEBANC'<br/>missing = 0"]
    G --> H["shrink past O, D, E<br/>window 'BANC', best = 4"]
    H --> I["drop 'B' → missing = 1<br/>loop ends, return 'BANC'"]

Code

java

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }
        int[] need = new int[128]; // how many more of each char the window needs
        for (char c : t.toCharArray()) {
            need[c]++;
        }
        int missing = t.length(); // required chars not yet covered
        int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (need[c] > 0) {
                missing--; // c fills a real requirement
            }
            need[c]--;

            // window covers t: record it and try to shrink
            while (missing == 0) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestStart = left;
                }
                char d = s.charAt(left);
                need[d]++;
                if (need[d] > 0) {
                    missing++; // we just removed a required char
                }
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}

Complexity

Time: O(m + n) — building need is O(n); left and right each move at most m times.
Space: O(1) — a fixed 128-slot array (the output substring aside).

Complexity Comparison

Approach	Time	Space
Brute Force	O(m² · 128)	O(1)
Sliding Window + full check	O(128 · m)	O(1)
Sliding Window + missing counter	O(m + n)	O(1)

Common Pitfalls

Ignoring duplicates in t: t = "AA" needs two 'A's — a set of required letters is not enough.
Decrementing missing for every character that enters, even surplus ones — only decrement when need[c] > 0 before the decrement.
Building s.substring(...) inside the loop for every candidate; store (start, length) and build the string once at the end.
Using a 26-slot array — s and t mix upper and lowercase letters, so index by the raw char (128 slots) or use 52.