76. Minimum Window Substring — LeetCode(Python)

I got you!

Problem:

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.

A substring is a contiguous sequence of characters within the string.

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.
Since the largest window of s only has one 'a', return empty string.

Constraints:

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

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution:

if t == '': return ''
        
t_dict, window = {}, {}
        
for c in t:
    t_dict[c] = 1 + t_dict.get(c, 0)
            
have, need = 0, len(t_dict)
res, resLen = [-1, -1], float('inf')
l = 0
        
for r in range(len(s)):
    c = s[r]
    window[c] = 1 + window.get(c, 0)
            
    if c in t_dict and window[c] == t_dict[c]:
        have += 1
                
    while have == need:
        # update our result
        if r - l + 1 < resLen:
            resLen = r - l + 1
            res = [l, r]
                    
        # pop from left of window
        window[s[l]] -= 1
        if s[l] in t_dict and window[s[l]] < t_dict[s[l]]:
            have -= 1
                    
        l += 1
                
l, r = res
return s[l:r+1]

Explanation —

We use a sliding window approach here.

We use two hash maps, t_dict for keeping count of the frequency of each element in t, and window for keeping count of the frequency of each element in the substring of s that we are considering.

If the frequency of an element in a given window is greater than or equal to the frequency of that element in t, we increment the number of matches we have.

When we encounter a new element in s, we update it’s frequency in the map window.

If this new character is present in t, and the frequency of the character in both dictionaries is the same for the first time, we increment the value of have.

When the number of matches we have is equal to the number of unique characters in t, we have found a substring.

So, when have == need, we update the value of resLen and res, where we store the length of the minimum window and the indices bounding that window respectively.

Next, we shrink the window from the left. The count of that element in the window is decremented. Any changes made to the number of matches are updated, and the left end of the window is slid.

Finally, we return the substring in s between the indices stored in res.

Time and Space Complexity —

In the worst case, we might end up traversing through each element in the string s twice, by both the pointers.

Also, the minimum window could be the entire string s, and t could possibly have all unique characters.

Thus, if S is the length of string s and T is the length of string t,

Time Complexity: O(S + T)

Space Complexity: O(S + T)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏