76. Minimum Window Substring

Hard LeetCode

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 "". The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.

Constraints:

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

How to solve the problem

• Brute Force O(n^3)

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

        result = set()
        t_count = Counter(t)

        for left in range(len(s)):
            for right in range(left,len(s)):
                window = Counter(s[left:right+1])
                if all(window[c] >= t_count[c] for c in t_count):
                    result.add(s[left:right+1])
        if not result:
            return ""

        return min(result,key=len)

• Sliding Window + HashMap

If have does not increase, it means we haven’t collected all the required characters yet; in this case, expanding the right pointer only makes the window larger and adds irrelevant characters. Once have == need, we must shrink the left side to remove the unnecessary characters and obtain the minimum window.

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        
        t_count = Counter(t)          # frequency of chars in t
        window = {}                   # frequency of chars in current window
        
        have, need = 0, len(t_count)  # how many chars meet the required freq, total needed
        res, res_len = [-1, -1], float("inf")  # best window boundaries and length
        
        left = 0
        for right, char in enumerate(s):
            # expand the window by including current char
            window[char] = window.get(char, 0) + 1
            
            # check if this char now satisfies the freq requirement
            if char in t_count and window[char] == t_count[char]:
                have += 1
            
            # when the window is valid, try to shrink it
            while have == need:
                # update result if this window is smaller
                if (right - left + 1) < res_len:
                    res = [left, right]
                    res_len = right - left + 1
                
                # remove leftmost char and shrink window
                window[s[left]] -= 1
                if s[left] in t_count and window[s[left]] < t_count[s[left]]:
                    have -= 1
                left += 1
        
        l, r = res
        return s[l:r+1] if res_len != float("inf") else ""

Complexity

• Time Complexity: O(n + m) - Where n is the length of string s and m is the length of string t. We traverse both strings once with the sliding window.
• Space Complexity: O(k) - Where k is the number of unique characters in string t. The hash map stores at most k characters.