Minimum Window Substring

hardSliding Window104 stepsJava · Python · C++

Find the smallest substring of s containing every character of t (with multiplicity). Expand right until the window covers t, then shrink from the left as long as it still covers, recording the smallest window seen.

▶ Watch the animated trace

Traced input: s = "ADOBECODEBANC", t = "ABC" → "BANC". Original problem: neetcode.io/problems/minimum-window-with-characters

Complexity

BestO(m + n)

AverageO(m + n)

WorstO(m + n)

SpaceO(1)

Each pointer moves at most |s| times; the counts use a fixed 128-size array.

Key idea

need[c] counts how many of each character are still missing.
missing is the total still needed; the window covers t when it hits 0.
While covered, record the window and move l right, putting characters back into need.
When a needed character leaves, missing goes up and you resume expanding.

Common mistakes

Treating t as a set; duplicates in t must be counted.
Returning the length instead of the substring.
Shrinking with if instead of while, which leaves windows too big.

Solution

Java

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++;
            }
            l++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
}

Python

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

C++

string minWindow(string s, string t) {
    int need[128] = {0};
    for (char c : t) need[c]++;
    int missing = t.size(), l = 0, bestL = 0, bestLen = INT_MAX;
    for (int r = 0; r < (int)s.size(); r++) {
        if (need[s[r]]-- > 0) {
            missing--;
        }
        while (missing == 0) {
            if (r - l + 1 < bestLen) {
                bestLen = r - l + 1;
                bestL = l;
            }
            if (++need[s[l]] > 0) {
                missing++;
            }
            l++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
t longer than s Two a's are needed but only one exists.	`s = "a", t = "aa"`	`""`
Exact match The whole string.	`s = "a", t = "a"`	`"a"`
Duplicates in t Three a's in a row at the end.	`s = "aaflslflsldkalskaaa", t = "aaa"`	`"aaa"`
Case sensitive 'a' does not count as 'A'.	`s = "aA", t = "A"`	`"A"`