Minimum Window Substring

HardSliding WindowBlind 75SeniorOpen on LeetCodeUpdated Sep 21, 2026

You're given two strings s and t. Return the shortest substring of s that contains every character of t, including duplicates: if t has two 'a's, the substring needs at least two 'a's. Order doesn't matter and extra characters are allowed. Matching is case-sensitive. If no such substring exists, return the empty string "". When an answer exists, it is unique.

Examples

s = "ADOBECODEBANC", t = "ABC" returns "BANC"

The shortest substring holding an A, a B and a C is "BANC".

"BANC" (indices 9 to 12) holds an A, a B and a C in 4 characters. Other substrings containing all three, such as "ADOBEC" and "CODEBA", are at least 6 long.

s = "a", t = "a" returns "a"

The whole string is the only substring, and it contains the one 'a' that t needs.

s = "a", t = "aa" returns ""

t needs two 'a's but s has only one, so no substring of s qualifies and the answer is the empty string.

Constraints

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

Hints

Hint 1

You need a range that contains every required character, when does shrinking it stop being valid?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Count how many of each character t needs, plus one counter, missing, for how many characters are still uncovered. Extend the window with right; a character lowers missing only if its need was still positive. When missing hits 0, record the window and shrink from the left until removing a needed character makes missing positive again. Each index enters and leaves once, and the count table is bounded by the alphabet.

Time

O(|s| + |t|)

Space

O(1)

Pitfall

Count letters with multiplicity. Decrement missing only when need[c] was above zero, and increment it only when a removal pushes need[c] back above zero. Otherwise surplus copies, like the second B in "ADOBECODEBANC", throw the counter off.

Solutions

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

from collections import Counter

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