LeetCode #76: Minimum Window Substring

LeetCode Solutions

https://leetcode.com/problems/minimum-window-substring/

To solve this problem in Python 3, we can use a sliding window approach that involves maintaining two dictionaries, count_t and count_window, to keep track of the count of each character in the t string and the current window, respectively.

Here are the steps to follow:

  1. Initialize the count_t dictionary to store the count of each character in the t string.
  2. Initialize the left and right pointers to the start of the string s, the count_window dictionary to an empty dictionary, and the required and formed variables to 0.
  3. Initialize the left_min variable to -1, the right_min variable to -1, and the min_len variable to infinity.
  4. Iterate through the string s using the right pointer and add each character to the count_window dictionary. If the count of the current character in the count_window dictionary is equal to the count of the same character in the count_t dictionary, increment the formed variable.
  5. While the formed variable is equal to the required variable, i.e., all characters in t are present in the current window, update the left_min, right_min, and min_len variables as necessary and shrink the window from the left by incrementing the left pointer and updating the count_window and formed variables.
  6. Return the minimum window substring.

Here’s the Python 3 code that implements this approach:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        count_t = {}
        for char in t:
            count_t[char] = count_t.get(char, 0) + 1
        
        left = 0
        right = 0
        count_window = {}
        required = len(count_t)
        formed = 0
        left_min = -1
        right_min = -1
        min_len = float('inf')
        
        while right < len(s):
            count_window[s[right]] = count_window.get(s[right], 0) + 1
            if s[right] in count_t and count_window[s[right]] == count_t[s[right]]:
                formed += 1
            
            while left <= right and formed == required:
                if right - left + 1 < min_len:
                    left_min = left
                    right_min = right
                    min_len = right - left + 1
                
                count_window[s[left]] -= 1
                if s[left] in count_t and count_window[s[left]] < count_t[s[left]]:
                    formed -= 1
                
                left += 1
            
            right += 1
        
        if left_min == -1:
            return ""
        else:
            return s[left_min:right_min+1]

Time Complexity

The time complexity of the above algorithm is O(|s| + |t|), where |s| and |t| are the lengths of the strings s and t, respectively.

The reason for this is that we iterate through the string s once using the right pointer and then shrink the window from the left using the left pointer. In the worst case, we need to iterate through the entire string s twice. Additionally, we iterate through the string t once to initialize the count_t dictionary.

Space Complexity

The space complexity of the above algorithm is O(|s| + |t|), where |s| and |t| are the lengths of the strings s and t, respectively.

The reason for this is that we use two dictionaries, count_t and count_window, to keep track of the count of each character in the t string and the current window, respectively. The size of these dictionaries can be up to the length of the strings s and t.