Minimum Window Substring#

Given two strings s and t, find the shortest contiguous substring of s that contains every character of t, counting duplicates. If no such window exists, return an empty string. When several windows tie for the shortest length, any one of them is acceptable.

Example#

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC", the shortest window of s that includes A, B, and C.

Brute force#

Check every substring of s and test whether it covers all required characters, keeping the shortest that does. Enumerating substrings and re-counting each is expensive.

• Time: O(n^2 * m) in the naive form.
• Space: O(m).

Optimal approach#

Slide a window with two pointers and keep counts of the characters you still need. Expand the right edge until the window covers all of t. Then shrink the left edge as far as possible while the window stays valid, recording the smallest valid window along the way. A running counter of how many required characters are currently satisfied lets you check validity in constant time per step.

Python solution#

 1from collections import Counter
 2
 3
 4def min_window(s, t):
 5    if not s or not t:
 6        return ""
 7    need = Counter(t)
 8    missing = len(t)
 9    left = 0
10    best_len = float("inf")
11    best_start = 0
12    for right, ch in enumerate(s):
13        if need[ch] > 0:
14            missing -= 1
15        need[ch] -= 1
16        while missing == 0:
17            if right - left + 1 < best_len:
18                best_len = right - left + 1
19                best_start = left
20            need[s[left]] += 1
21            if need[s[left]] > 0:
22                missing += 1
23            left += 1
24    return "" if best_len == float("inf") else s[best_start:best_start + best_len]

Complexity#

• Time: O(n + m), each character of s enters and leaves the window once.
• Space: O(m) for the character counts of t.

This problem is the hardest workout for the sliding window technique. Keep practicing with the 60-day challenge.