Minimum Window Substring

Hard Problem 26 of 151 Java and Python

Problem

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

The answer is guaranteed to be unique when it exists.

Example 1

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

Example 2

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

Example 3

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

Constraints

1 ≤ s.length, t.length ≤ 10⁵
s and t contain uppercase and lowercase English letters.

Explanation

Expand the right edge until the window covers everything in t. Then shrink from the left as far as possible while it still covers t, recording the smallest valid window. Repeat.

To check "covers t" in O(1), count how many characters are still missing. Adding a needed character lowers it; removing one raises it.

Approach 1 · Naive

Check every substring

Time O(n² · k), k = distinct letters
Space O(k)

For every start, extend the end until the window contains all of t; that is the shortest valid window from this start.

Count the characters of t.
For each i, extend j while updating window counts, until every needed count is met.
Keep the shortest such window.

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

Python

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        best = ""
        for i in range(len(s)):
            have = Counter()
            for j in range(i, len(s)):
                have[s[j]] += 1
                if all(have[c] >= n for c, n in need.items()):
                    if not best or j - i + 1 < len(best):
                        best = s[i:j + 1]
                    break
        return best

Approach 2 · Optimal

Expand, then shrink

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

Track missing, the number of characters of t not yet covered. Expand right; when missing hits 0, shrink left as long as the window stays valid, recording the best.

Count need[c] for t; set missing = t.length.
For each right: if need[s[right]] > 0, decrement missing. Then decrement need[s[right]] (it may go negative for extras).
While missing == 0: record the window if smaller; increment need[s[left]]; if it becomes positive, increment missing; move left.

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();
        int left = 0;
        int bestStart = 0;
        int bestLength = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            if (need[s.charAt(right)]-- > 0) {
                missing--;
            }
            while (missing == 0) {
                if (right - left + 1 < bestLength) {
                    bestStart = left;
                    bestLength = right - left + 1;
                }
                if (++need[s.charAt(left)] > 0) {
                    missing++;
                }
                left++;
            }
        }
        return bestLength == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLength);
    }
}

Python

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        missing = len(t)
        left = 0
        best = (0, float("inf"))
        for right, c in enumerate(s):
            if need[c] > 0:
                missing -= 1
            need[c] -= 1
            while missing == 0:
                if right - left < best[1] - best[0]:
                    best = (left, right)
                need[s[left]] += 1
                if need[s[left]] > 0:
                    missing += 1
                left += 1
        return "" if best[1] == float("inf") else s[best[0]:best[1] + 1]

Complexity compared

Approach	Time	Space
Naive Check every substring	O(n² · k), k = distinct letters	O(k)
Optimal Expand, then shrink	O(n + m)	O(k)

Key takeaways

Shortest-window problems: expand until valid, then shrink while valid.
Letting counts go negative for surplus characters avoids a second map.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem