76. Minimum Window Substring

Problem¶

Given strings s and t, return the shortest substring of s containing every character of t with at least the same frequency, or "" if none exists.

s = "ADOBECODEBANC", t = "ABC" -> "BANC"

Key trick¶

Use a sliding window: expand the right boundary until all required characters are present, then advance the left boundary while the window remains valid.

Trap¶

Checking all character counts whenever the window changes can make the algorithm slower than \(O(m+n)\).
Duplicates in t must be counted.
Repeatedly storing substring slices can introduce unnecessary copying; store the best boundaries instead.

Why is it interesting?¶

It combines frequency tracking with a variable-size sliding window while ensuring each pointer moves at most once across s.

Python solution¶

from collections import Counter


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

        need = Counter(t)
        missing = len(t)
        l = 0
        best_start = 0
        best_len = len(s) + 1

        for r, ch in enumerate(s):
            # A positive count means this occurrence is still needed.
            if ch in need:
                if need[ch] > 0:
                    missing -= 1
                need[ch] -= 1

            # Shrink every valid window to find its shortest valid suffix.
            while missing == 0:
                window_len = r - l + 1
                if window_len < best_len:
                    best_start = l
                    best_len = window_len

                left_ch = s[l]
                if left_ch in need:
                    need[left_ch] += 1
                    if need[left_ch] > 0:
                        missing += 1
                l += 1

        if best_len > len(s):
            return ""
        return s[best_start : best_start + best_len]

Time complexity: \(O(|s|+|t|)\).

Space complexity: \(O(|t|)\).

Comment on my solution¶

Your sliding-window logic is correct, concise, and handles duplicate characters.

However, counts <= window compares all tracked counts on every loop check, so the worst-case time can exceed \(O(m+n)\). Assigning s[l:r+1] whenever a better window is found also repeatedly copies substrings. Tracking a scalar number of missing characters and saving only the best boundaries avoids both issues.

from collections import Counter

# WORKS
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # "ADOBECODEBANC", "ABC" -> "BANC"
        # "a", "a"  -> "a"
        # "a", "aa" -> ""
        ans = ""
        counts = Counter(t)
        window = Counter()
        l = 0
        for r, ch in enumerate(s):
            if ch in counts:
                window[ch] += 1
            while counts <= window:
                if not ans or r - l + 1 < len(ans):
                    ans = s[l:r+1]
                if s[l] in counts:
                    window[s[l]] -= 1
                    if window[s[l]] == 0:
                        del window[s[l]]
                l += 1
        return ans