HardLeetCode #76Sliding Window

Minimum Window Substring

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 "".

Constraints

m == s.length, n == t.length, 1 <= m, n <= 10^5

Examples

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

Output: "BANC"

Solution Approach

Sliding window with two pointers. Expand right to include all chars, contract left when valid.

Implementation

def minWindow(s, t):
    if not t or not s:
        return ""
    
    dict_t = {}
    for char in t:
        dict_t[char] = dict_t.get(char, 0) + 1
    
    formed = 0
    required = len(dict_t)
    window_counts = {}
    l, r = 0, 0
    result = float("inf"), None, None
    
    while r < len(s):
        char = s[r]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        if char in dict_t and window_counts[char] == dict_t[char]:
            formed += 1
        
        while l <= r and formed == required:
            char = s[l]
            if r - l + 1 < result[0]:
                result = (r - l + 1, l, r)
            
            window_counts[char] -= 1
            if char in dict_t and window_counts[char] < dict_t[char]:
                formed -= 1
            l += 1
        
        r += 1
    
    return "" if result[0] == float("inf") else s[result[1]:result[2] + 1]

Complexity Analysis

Time Complexity

O(m + n)

Space Complexity

O(m + n)

Complexity

Time:O(m + n)

Space:O(m + n)

Hints

1.Use two hash maps for needed and current window counts
2.Track how many unique chars are satisfied
3.Shrink window when all chars satisfied

Asked at

Google