Minimum Window Substring

The brute force checks every substring of s and asks “does this contain all of t?” The optimal approach flips the search around: grow a window with right until it does contain everything t needs, then greedily shrink it from left for as long as it still qualifies, recording the smallest valid window seen. Each valid window found this way is a candidate for the answer; we never need to re-examine a window from scratch.

Brute Force

Time O(m² · n)Space O(n)

For every starting index i, extend j outward and check (via a frequency count) whether the substring s[i:j+1] contains all of t, stopping at the first success since further growth would only lengthen it.

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        n = len(s)
        best = ""
        for i in range(n):
            count = Counter()
            missing = len(t)
            for j in range(i, n):
                if count[s[j]] < need[s[j]]:
                    missing -= 1
                count[s[j]] += 1
                if missing == 0:
                    if best == "" or j - i + 1 < len(best):
                        best = s[i:j + 1]
                    break
        return best

Why it’s slow: for each of the m starting indices, we may scan up to m characters forward while updating a frequency count of size n — O(m² · n) in the worst case. It never reuses the counting work done for a nearby starting index.

Sliding Window (Expand and Contract)

OptimalTime O(m + n)Space O(n)

Keep a need count of characters still required (this can go negative for characters we have “extra” of) and a missing counter for how many more characters (with multiplicity) are needed to satisfy t. Expand right, decrementing need for each character consumed and missing whenever a needed character is used up. Once missing hits 0 the window is valid: shrink left past any characters that are not actually needed (where need has gone negative), record the window if it beats the best seen so far, then release one character from the left side and keep going.

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""

        need = Counter(t)
        missing = len(t)
        left = 0
        best_left, best_right = 0, 0

        for right, ch in enumerate(s, 1):
            if need[ch] > 0:
                missing -= 1
            need[ch] -= 1

            if missing == 0:
                while need[s[left]] < 0:
                    need[s[left]] += 1
                    left += 1
                if best_right == 0 or right - left < best_right - best_left:
                    best_left, best_right = left, right
                need[s[left]] += 1
                missing += 1
                left += 1

        return s[best_left:best_right]

Tracing s = "ADOBECODEBANC", t = "ABC":

left

right

best = 6

1 / 5

comparingseenresultdiscarded

Window [0,5] = ADOBEC first contains all of A, B, and C. Record length 6 as the best so far.

Correctness: every time missing reaches 0 the window [left, right) is a valid superset of t’s characters (with multiplicity); the inner while loop only ever discards characters that are already in surplus (need[...] < 0), so it never breaks validity while shrinking. Every valid window that exists is encountered as right sweeps forward, so the true minimum is among the recorded candidates.

Complexity: right advances through s once and left never moves backward, so each pointer does at most m steps of work — O(m) overall, plus O(n) to build the initial need counter — O(m + n) time. The counters hold at most O(n) distinct characters from t — O(n) space.