HardBlind75StringSliding WindowHash Table

Minimum Window Substring

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

Examples

Input
s = 'ADOBECODEBANC', t = 'ABC'
Output
'BANC'

The minimum window substring 'BANC' includes 'A', 'B', and 'C'.

Input
s = 'a', t = 'a'
Output
'a'

The entire string s is the minimum window.

Constraints

  • •m == s.length
  • •n == t.length
  • •1 <= m, n <= 10^5
  • •s and t consist of uppercase and lowercase English letters.

Approaches

For each substring of s, check if it contains all characters of t.

CodeT: O(m^2 * n) | S: O(m + n)
from collections import Counter

def min_window(s, t):
    t_count = Counter(t)
    min_len = float('inf')
    result = ''
    for i in range(len(s)):
        for j in range(i + len(t), len(s) + 1):
            window = s[i:j]
            window_count = Counter(window)
            if all(window_count[c] >= t_count[c] for c in t_count):
                if j - i < min_len:
                    min_len = j - i
                    result = window
    return result

Expand the window until all characters of t are included, then shrink from the left.

CodeT: O(m + n) | S: O(m + n)
from collections import Counter, defaultdict

def min_window(s, t):
    if not s or not t:
        return ''
    t_count = Counter(t)
    required = len(t_count)
    formed = 0
    window_counts = defaultdict(int)
    left = 0
    min_len = float('inf')
    min_left = 0
    for right in range(len(s)):
        char = s[right]
        window_counts[char] += 1
        if char in t_count and window_counts[char] == t_count[char]:
            formed += 1
        while formed == required:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in t_count and window_counts[left_char] < t_count[left_char]:
                formed -= 1
            left += 1
    return '' if min_len == float('inf') else s[min_left:min_left + min_len]

Same sliding window but with a cleaner implementation using missing count.

Diagram

s='ADOBECODEBANC', t='ABC' Expand until 'ABC' covered: 'ADOBEC' (6) Shrink: 'DOBEC' no 'A', stop Expand: ... 'CODEBANC' (9) Shrink: 'BANC' (4) has 'ABC' -> best Return 'BANC'
CodeT: O(m + n) | S: O(m + n)
from collections import Counter

def min_window(s, t):
    if not s or not t:
        return ''
    need = Counter(t)
    missing = len(t)
    left = 0
    best_start, best_len = 0, float('inf')
    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        while missing == 0:
            window_len = right - left + 1
            if window_len < best_len:
                best_len = window_len
                best_start = left
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return '' if best_len == float('inf') else s[best_start:best_start + best_len]

Complexity Comparison

Brute Force
T: O(m^2 * n)S: O(m + n)

For each substring of s, check if it contains all characters of t.

Sliding Window with HashMap
T: O(m + n)S: O(m + n)

Expand the window until all characters of t are included, then shrink from the left.

Optimized Sliding Window
T: O(m + n)S: O(m + n)

Same sliding window but with a cleaner implementation using missing count.

Common Mistakes

Not handling characters in t that appear more times than in the window

Using a set instead of a counter to handle duplicate characters in t

Forgetting to return empty string when no valid window exists

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems