LeetEye LeetEye
Medium Sliding Window ~5 min

Minimum Window Substring

sliding-window minimum-window-substring

Problem

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Examples

Example 1
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
"BANC" is the smallest window containing 'A', 'B', and 'C'.
Example 2
Input: s = "a", t = "a"
Output: "a"
Example 3
Input: s = "a", t = "aa"
Output: ""
Need two 'a's but only one exists.
Key Insight

Expand window until valid (contains all of t). Then shrink from left while still valid. Track minimum.

Expand right until valid, shrink left while still valid, track minimum. Validity = all target chars satisfied.

How to Approach This Problem

Pattern Recognition: When you see keywords like minimum window substring sliding-window, think Sliding Window.

Step-by-Step Reasoning

1 We use sliding window because:
Answer: We're looking for a contiguous substring
Substring = contiguous sequence. Window maintains contiguity.
2 A window is valid when:
Answer: It contains each char from t with at least the required frequency
If t = "aab", window needs at least 2 'a's and 1 'b'. Frequencies matter.
3 We expand the window when:
Answer: Window is not yet valid
Need to include more chars to meet the requirement. Once valid, try shrinking.
4 Once window is valid, we shrink from left to:
Answer: Find a smaller valid window
We want minimum window. Maybe some chars on the left aren't needed. Shrink until invalid, track min valid.
5 To efficiently check if window contains all of t:
Answer: Track "how many char requirements are fully met"
For each char in t, track if window has enough. Count how many chars have met quota. When count equals unique chars in t, window is valid.
6 We update our answer (minimum window) when:
Answer: Window is valid and smaller than current best
Only valid windows count. Among valid, we want smallest.

Solution

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""
    
    from collections import Counter
    t_count = Counter(t)
    required = len(t_count)
    
    left = 0
    formed = 0
    window_count = {}
    ans = (float('inf'), None, None)  # (length, left, right)
    
    for right in range(len(s)):
        char = s[right]
        window_count[char] = window_count.get(char, 0) + 1
        
        if char in t_count and window_count[char] == t_count[char]:
            formed += 1
        
        # Shrink window while valid
        while formed == required:
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            
            left_char = s[left]
            window_count[left_char] -= 1
            if left_char in t_count and window_count[left_char] < t_count[left_char]:
                formed -= 1
            left += 1
    
    return "" if ans[0] == float(&#039;inf') else s[ans[1]:ans[2]+1]

Complexity Analysis

Time O(|s| + |t|)
Space O(|s| + |t|)

Master This Pattern

Build intuition with interactive MCQs. Practice Sliding Window problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye