Minimum Window Substring Solution

Problem

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

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the shortest substring of s that contains A, B, and C.

If t contains duplicate characters, the window must cover each one at least that many times — t = "AA" requires at least two A's in the window, not one.

Input: s = "A", t = "AA"
Output: ""
Explanation: There is only one A in s, so no window can satisfy t = "AA".

Intuition

The problem asks you to find the tightest frame over s that covers everything in t. Once a window becomes valid, extending the right edge further can only make it longer — so the right move is to try shrinking from the left. This expand-then-shrink rhythm, where each pointer moves in only one direction, is the defining shape of the sliding window pattern.

Approach 1 — Brute Force

Try every possible starting position and, from there, extend right until the window first satisfies all character requirements. Since extending any further would only make the window longer, move to the next starting position after recording the best result.

Build a frequency map of characters needed from t and count how many distinct character types that is.
For each starting index, create a fresh window counter and a satisfied counter.
Advance the end pointer one character at a time; when a character's window count exactly hits its required count, increment satisfied.
Once all types are satisfied, record the substring if it is shorter than the current best, then break to the next start.
Return the best substring found, or "" if none.

1def minWindow(s: str, t: str) -> str:
2    from collections import Counter
3    need = Counter(t)
4    best = ""
5
6    for start in range(len(s)):
7        window = Counter()
8        for end in range(start, len(s)):
9            window[s[end]] += 1
10            # Valid when every character type in t appears enough times
11            if all(window[char] >= need[char] for char in need):
12                if not best or end - start + 1 < len(best):
13                    best = s[start:end + 1]
14                break  # Extending right from this start can only make it longer
15    return best

Time: O(n² · |t|) — two nested loops over s, with an O(|t|) validity check at each inner step in the Python version; the Java/C++ versions reduce that inner check to O(1) but the nested loops remain. Space: O(|t|) — for the character frequency structures.

Approach 2 — Sliding Window

Maintain a single window using two pointers that only move right. Expand right until the window covers all of t, then shrink left as far as possible while keeping it valid, recording the minimum length at each valid state.

Build a need map from t with character frequencies; set required to the number of distinct character types.
Track have — how many distinct types are currently satisfied in the window (window count ≥ needed count).
Advance right, adding each character to the window; when a character's window count exactly reaches its required count, increment have.
When have == required, the window is valid — record it if shortest so far, then advance left; if removing the left character drops its window count below its required count, decrement have.
Repeat until right has passed the end of s.

1def minWindow(s: str, t: str) -> str:
2    if not s or not t:
3        return ""
4
5    need = {}
6    for char in t:
7        need[char] = need.get(char, 0) + 1
8
9    window = {}
10    have, required = 0, len(need)  # required = number of distinct types in t
11    left = 0
12    min_len, min_left = float("inf"), 0
13
14    for right in range(len(s)):
15        char = s[right]
16        window[char] = window.get(char, 0) + 1
17        # Only increment have when the count exactly reaches the requirement
18        if char in need and window[char] == need[char]:
19            have += 1
20
21        while have == required:
22            if right - left + 1 < min_len:
23                min_len = right - left + 1
24                min_left = left
25            left_char = s[left]
26            window[left_char] -= 1
27            # Dropping below the requirement means this type is no longer satisfied
28            if left_char in need and window[left_char] < need[left_char]:
29                have -= 1
30            left += 1
31
32    return s[min_left:min_left + min_len] if min_len != float("inf") else ""

Time: O(n + m) — each character in s is visited at most twice (once by right, once by left); building need takes O(m). Space: O(m) — the window and need structures hold at most O(distinct chars in t) entries.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n² · m)	O(m)	Only for very short inputs where exhaustive checking is acceptable
Sliding Window	O(n + m)	O(m)	All practical cases — this is the expected interview solution

Common Mistakes

Miscounting duplicate characters — if t = "AA", you need at least two A's. Satisfying have with a boolean per character breaks this; have must only increment when the window count exactly reaches the required count (not simply when it becomes nonzero).
Incrementing have more than once per type — because have tracks how many types are satisfied, you must check window[c] == need[c] (exact match), not >=. Checking >= would increment have every time you see that character after it's already satisfied.
Wrong condition when shrinking — when removing the left character, decrement have only if window[c] < need[c] (strictly less than), not <=. Using <= would incorrectly lose satisfaction when the window still has exactly the right count.
Off-by-one in the result extraction — the result is s[min_left : min_left + min_len] in Python and s.substring(minLeft, minLeft + minLen) in Java. Using right as the upper bound gives the current window, not the recorded minimum.
Forgetting the no-valid-window case — if min_len never updates from its sentinel value (infinity or INT_MAX), there is no valid window and you must return "", not a zero-length slice of s.

Minimum Window Substring — Solution