How to get a minimum substring using the sliding window algorithm?

For a given string, to get the minimum substring that contains all the characters we want is not easy to do. When screening through the string, we always use an algorithm called “sliding window” which uses two pointers to locate the substring. In this post, I’ll introduce this algorithm by solving this problem together: minimum window substring.

Problem Description

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "a", t = "a"
Output: "a"

Before solving this problem, let’s take a look at the Sliding Window algorithm.

Sliding Window Algorithm

The Sliding Window algorithm is to form a “window” in data, this window will slide around the data to grasp the part as desired.

One classic example is to find the window sum of a list. For the given array and integer k, move the window at each iteration from the start of the array, find the sum of elements inside the window at each move. For example, when Input array=[1,2,7,5,8], k = 3, Output：[10,14,20] . We can form a window with size k, after calculating the sum of the current window, we move the window to it’s right until we met the end of the array. The following graph will help illustrate how it works:

Solution

To find the substring of string s that contains all characters from the string t, we can have a window in string s to help. The window is defined by two pointers: the left and right pointer. The substring starting from index left ends at index right is the minimum substring as desired. The key point is: how does the window slide in the string? That depends on how and when does the left and right pointers move:

• The right pointer is responsible for finding a substring that has all the characters of string t.
• The left pointer is contacting the substring to make sure the current substring has the minimum length. We only move the left pointer if the current substring has all the characters of string t.

When the right pointer meets the end of string s, meaning that we’ve looked through all the substrings. Finally, the substring between the left and right pointer is the result we want.

Let’s go over the steps together to see how the sliding window algorithm works on this problem. Assume we are given the string s = "ABAACBAB", t = "ABC"

Step 1:

Initialize the left and right pointers, they all begin from the first character of the string s.

Step 2:

We gradually move the right pointer to its right, until it forms a valid window that contains all the characters of string t, records the current window.

Step 3:

Now move the left pointer to its right, if we find the smaller window, we update the result with a smaller size.

Step 4:

We gradually move the left pointer until we find out that the current window is no longer valid(the current window doesn't contain all the characters of string t), we repeat step 1 to find a new valid window.

Step 5:

Repeat step 3 to contact the window and update the result with the smaller size.

Step 6:

Right pointer meets the end, done. And we’ve found the minimum substring.

Code

    def minWindow(self, s: str, t: str) -> str:
        
        if not s or not t:
            return ''
       #assign two pointers        
       left, right = 0, 0
        
        dict_t = Counter(t)
        required = len(dict_t)
        formed = 0 
        window_counts = {}
        ans = float("inf"), None, None
        
#move the right pointer to find the window       
        while right < len(s):
            char = s[right]
            window_counts[char] = window_counts.get(char, 0) + 1
            
            if char in dict_t and window_counts[char] == dict_t[char]:
                formed += 1
            
            #move the left pointer to contact the window
            while left <= right and formed == required:
                char = s[left]
                
                if right - left + 1 < ans[0]:
                    ans = (right -left+1, left, right)
                    
                window_counts[char] -= 1
                
                if char in dict_t and window_counts[char] < dict_t[char]:
                    formed -= 1
                
                left += 1
            
            right += 1
            
        return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

Complexity Analysis

• Time complexity: O(|S| + |T|)O(∣S∣+∣T∣) where |S| and |T| represent the lengths of strings s and t.
• Space complexity: O(∣S∣+∣T∣) due to it creates two dictionaries to tell whether the current window is valid or not.