Leetcode 76. Minimum Window Substring

Problem

Leetcode 76 - Minimum Window Substring

Example:

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

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

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Approach

We can solve this problem by using sliding window technique.

1. Initialize 2 dictionary called countT, window
   • countT will store frequency of each character in t
   • window will store frequency of each character in substring s
2. Count the frequency of each letter in string t
3. Have 2 variables have, need
   • have is counting how many character is window[c] == countT[c]
   • window to count the frequency of window in s
4. Initialize result variables ‘res’, ‘resLen’
   • res to get the index of substring
   • resLen to track minimum substring length
5. Initialize left pointer
6. Start the for loop on s
   1. increment the value for window[s[right]]
   2. if s[right] is in countT and countT[s[right]] == window[s[right]]
      1. increment have
   3. while have == need, we’ve met the requirement to be substring, thus we need to move the window
      1. If right-left+1 < resLen
         1. update res, and resLen
      2. decrement the value for window[s[left]]
      3. if s[left] is in countT and countT[s[left]] < window[s[left]]
         1. decrement have
      4. move the left pointer
7. Since for loop is now done, we can get min length substring index (left, right)
8. return the substring s[left:right+1] if resLen != infinity else ‘’

Here is the Python code for the solution:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # if t is longer than s, can't be substring thus return ''
        # if t is empty, then there's no substring thus return ''
        if len(t) > len(s) or t == '':
            return ''
        
        # countT to count the frequency of t
        # window to count the frequency of window in s
        countT, window = {}, {}

        # counting the frequency of t
        for c in t:
            countT[c] = 1 + countT.get(c, 0)
        
        # have is counting how many character is window[c] == countT[c]
        # need is how many characters we need to be equal to
        have, need = 0, len(countT)
        res, resLen = [-1, -1], float('infinity')
        left = 0

        for right in range(len(s)):
            # increment the frequency of window
            c = s[right]
            window[c] = 1 + window.get(c, 0)

            # if that character is in countT, and has equal frequency, increment have
            if c in countT and window[c] == countT[c]:
                have += 1
            
            # if we meet the requirement of have == need
            while have == need:
                # update the result length to get min substring
                if (right - left + 1) < resLen:
                    resLen = right-left+1
                    res = [left, right]
                
                # move the window
                window[s[left]] -= 1
                
                # if that character is in countT, and has less frequency, decrement have
                if s[left] in countT and window[s[left]] < countT[s[left]]:
                    have -= 1
                left += 1
        
        # return result
        left, right = res
        return s[left:right+1] if resLen != float('infinity') else ''

Time Complexity and Space Complexity

Time Complexity: $O(n)$ where $n$ is the length of the string s

Space Complexity: $O(m)$ where $m$ is the total number of unique charactrs in s and t