We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Window Substring

Difficulty: Hard

Problem Description

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

Key Insights

  • The problem requires finding a substring in s that contains all characters from t, including duplicates.
  • A sliding window approach can efficiently find the minimum window by expanding and contracting the window size.
  • A hash table (or dictionary) can be used to keep track of the required characters and their counts from string t.
  • The solution must operate in O(m + n) time complexity to handle the upper limits of string lengths.

Space and Time Complexity

Time Complexity: O(m + n)
Space Complexity: O(n)

Solution

To solve the problem, we will use a sliding window approach combined with a hash table to keep track of the character counts required from string t. The process involves the following steps:

  1. Use a dictionary to count the frequency of each character in t.
  2. Initialize two pointers to represent the current window in s.
  3. Expand the right pointer to include characters until all required characters from t are in the current window.
  4. Once all characters are included, attempt to contract the left pointer to find the minimum window.
  5. Keep track of the minimum window size and update it whenever a smaller valid window is found.
  6. Return the minimum window substring or an empty string if no valid window exists.

Code Solutions

def min_window(s: str, t: str) -> str:
    from collections import Counter, defaultdict

    if not t or not s:
        return ""

    dict_t = Counter(t)
    required = len(dict_t)

    l, r = 0, 0
    formed = 0
    window_counts = defaultdict(int)
    
    min_len = float("inf")
    min_window = (0, 0)

    while r < len(s):
        character = s[r]
        window_counts[character] += 1
        
        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1
        
        while l <= r and formed == required:
            character = s[l]

            # Save the smallest window and update min_len
            if r - l + 1 < min_len:
                min_len = r - l + 1
                min_window = (l, r)

            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1
            
            l += 1
        
        r += 1

    return "" if min_len == float("inf") else s[min_window[0]: min_window[1] + 1]
← Back to All Questions