Minimum Window Substring

Hard Arrays & Hashing Sliding Window · Hash Map Original on LeetCode

Minimum Window Substring is a hard arrays & hashing problem solved with the sliding window · hash map pattern. The best approach, optimal (sliding window with a missing counter), runs in O(m + n) time and O(1) space. Below are 2 approaches in Java, from brute force up.

Problem

Given strings s and t, return the shortest substring of s that contains every character of t, including duplicates. If there is none, return the empty string. The answer is unique when it exists.

Examples

Example 1

Input: s = "XADOBECODEBANCY", t = "ABC"
Output: "BANC"

Example 2

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

Example 3

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

Constraints

1 <= s.length, t.length <= 10^5
Upper and lower case letters; duplicates in t must be matched.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force	`O(n² · 52)`	`O(1)`
Optimal (sliding window with a missing counter)	`O(m + n)`	`O(1)`

1Brute force

TimeO(n² · 52)Each of the O(n²) windows checks up to 52 letter counts.

SpaceO(1)

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

For each i, build counts while extending j.
When every needed count is satisfied, compare lengths and break.

Java

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        String best = "";
        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 (best.isEmpty() || j - i + 1 < best.length()) best = s.substring(i, j + 1);
                    break;
                }
            }
        }
        return best;
    }

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

2Optimal (sliding window with a missing counter)

TimeO(m + n)Each index enters and leaves the window once.

SpaceO(1)A fixed 128-entry count array.

Keep need[c] for each character and a counter missing of characters of t not yet covered. Expanding r lowers need; when need[c] was positive, one fewer is missing. When missing is 0 the window covers t: record it, then shrink from the left, and once a needed character leaves, missing becomes 1 again.

need[c] = count in t; missing = t.length.
For each r: if need[s[r]] > 0, missing--; need[s[r]]--.
While missing == 0: record [l, r]; need[s[l]]++; if need[s[l]] > 0, missing++; l++.

Java

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        int missing = t.length(), l = 0, bestL = 0, bestLen = Integer.MAX_VALUE;
        for (int r = 0; r < s.length(); r++) {
            if (need[s.charAt(r)]-- > 0) missing--;
            while (missing == 0) {
                if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
                if (++need[s.charAt(l++)] > 0) missing++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
    }
}

Edge cases to test

t has repeated characters
t longer than s
No valid window

Hints

Hint 1

Track how many characters of t still need to be covered, not just which ones.

Hint 2

Expand right until covered, then shrink left as far as possible.

FAQ

What is the best time complexity for Minimum Window Substring?

Optimal (sliding window with a missing counter) runs in O(m + n) time and O(1) extra space. Each index enters and leaves the window once.

Which pattern does Minimum Window Substring use?

It is a arrays & hashing problem that uses the sliding window · hash map pattern. Other problems with the same pattern: Number of Substrings Containing All Three Characters.

Is there a brute force solution for Minimum Window Substring?

Yes. Brute force takes O(n² · 52) time and O(1) space. For each start index, extend until the window covers t, and keep the shortest.

Which edge cases should I test for Minimum Window Substring?

t has repeated characters; t longer than s; No valid window.