Cracking the Minimum Window Substring Problem

The Minimum Window Substring is a problem on leetcode that involves finding the smallest contiguous substring ‘t’ within another string ‘s’. This substring, often referred to as a ‘window’, must contain every character present in ‘t’.

Here’s an example,

Consider a string s = ‘abbcbcba’ and another string t = ‘abc’

The minimum window substring would be ‘cba’ which includes all the characters from string ‘t’.

Brute Force Approach:

In this technique we generate all substrings of the string ‘s’. For each substring we check if it contains all the characters from string ‘t’ and check all the substrings to find the minimum substring.

Generation of all possible substrings will take O(n²) time complexity and checking for the minimum substring will take O(n). Hence the overall time complexity remains O(n²), which is not the optimal way of solving this problem.

Sliding Window Technique:

This technique is optimal because it allows us to dynamically adjust a window that slides through the array. The window expands to the right to try and include all characters from string t and contracts from the left to ensure that the substring is of the minimum length while still containing all the necessary characters.

Lets see a visual representation of how the code works!

window_count: stores the frequency of characters in the current window

target_count: stores the frequency of characters in string ‘t’.

have = 0, need = len(target_count): help us check if we have found a substring.

res = [-1, -1]: tracks the start and end indices of the minimum substring.

resLen = ∞: tracks the minimum length of substring found so far.

Working of sliding window for finding the minimum window substring

Let’s go through the above image for a better understanding of how a sliding window would work!

Walk-through:

1. We start by expanding our window to the right of the string ‘s’ and keep adding characters to window_count. We do this till have==need.
2. If we observe step 5, we have encountered this condition and so we have found a valid substring which contains all characters from string ‘t’. We store the res and resLen.
3. Now that we have found a substring, we aim to minimise the substring, so we start contracting the window from the left. This continues until the condition have==need is broken, which happens in step 6.
4. As the condition is broken, we again start expanding the window to the right to start finding a valid substring.
5. If we observe step 10, we have again satisfied the condition have==need. So we check the length of the substring which is more than the substring we found in step 5 so we don’t update the variables res and resLen.
6. Now as we found a substring we again started contracting the window from the left. We keep on doing it while we make sure we don’t break the have==need condition.
7. If we observe step 14, we have contracted the window from the left enough to be minimum and found a valid substring again while still satisfying the condition have==need.
8. Now this substring is of minimum length than the one we found in step 5, so we update res and reLen with new values.

Python Implementation:

class Solution(object):
    def minWindow(self, s, t):

        #base condition
        if t == "":
            return ""
        
        window = {}
        target = Counter(t)
        
        have, need = 0 , len(target)
        res, resLen = [-1, -1], float("infinity")
        left, right = 0, 0

        while right < len(s):

            character = s[right]

            #expanding window to right
            window[character] = window.get(character,  0) + 1

            if character in target and window[character] == target[character]:
                have += 1
            
            #found a substring
            while have == need:

                #update the minimum window substring
                if(right - left + 1) < resLen:
                    res = [left, right]
                    resLen = right - left + 1
                
                #contracting window from left
                window[s[left]] -= 1
                if s[left] in target and window[s[left]] < target[s[left]]:
                    have -= 1
                
                left += 1
            
            right += 1

        start_index, end_index  = res
        return s[start_index: end_index + 1] if resLen != float("infinity") else ""    

Time complexity:

As we are using a sliding window which goes through the entire string ONCE, it will take O(N) time complexity.

Thanks for reading! Happy Coding!