Introduction

In this article, we are going to solve an algorithm problem. The problem can be found on LeetCode - 76. Mininum Window Substring. It’s considered as a hard level problem on LeetCode.

Description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Solutions

Brute force

A brute force solution is to find all possible substrings in S with nested loops and compare them to T. The index of the outer loop and the index of the inner loop represent respectively the starting index and the ending index of the substring to be compared with T. If we ignore the time of string comparison, the time complexity of the brute force solution is O(N^2) with N the length of S.

Sliding window

It’s possible to solve this problem with a sliding window approach.

Algorithm

1. We start with two pointers l and r initially pointing to the first element of the string S.
2. We use the r pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of T.
3. Once we get a desirable window, we can move the l pointer ahead one by one. If the window is still a desirable one we keep on updating the mininum window size.
4. If the window is not desirable any more, we repeat step 2 onwards.

Details

• How do we know the current window becomes desirable?

  Use a missing variable to store the number of missing characters in the current window. If missing equals to 0, then the current window becomes desirable.

• How to update the variable missing efficiently?

  Use a map to store the occurrence of characters in T, use another map to store the occurrence of characters in the current window. When a character is added to the current window (when moving the r pointer ahead), if the occurrence of the character in the current window is smaller than or equal to the occurrence of it in the string T, then reduce the variable missing by 1; When a character is removed from the current window (when moving the l pointer ahead), if the occurrence of the character in the current window is smaller than the occurrence of it in the string T, then increase the variable missing by 1.

Code

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(s) < len(t):
            return ""

        ans = float("inf"), None, None
        
        self.dict_t = self._get_char_occ(t)
        self.missing = len(t)
        self.window = {}
        
        l, r = 0, 0
        while r < len(s):
            self._add(s[r])
            while l <= r and self.missing == 0:  # desirable window
                if r - l + 1 < ans[0]:
                    ans = r - l + 1, l, r
                self._remove(s[l])
                l += 1
            r += 1
        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]
    
    def _get_char_occ(self, a_string):
        occ = {}
        for c in a_string:
            occ[c] = occ.get(c, 0) + 1
        return occ
        
    def _add(self, c):
        """Add the given character to the current window 
        and update missing if necessary.
        """
        self.window[c] = self.window.get(c, 0) + 1
        # After the addition, the current window is 
        # 1 missing character closer to the string T on condition that
        # the occurrence of the character in the current window is 
        # LE the occurrence of the character in the string T
        if c in self.dict_t and self.window[c] <= self.dict_t[c]:
            self.missing -= 1
        
    def _remove(self, c):
        """Remove the given character from the current window 
        and update missing if necessary.
        """
        self.window[c] -= 1
        # After the removal, the current window is 
        # 1 missing character further from the string T on condition that
        # the occurrence of the character in the current window is 
        # LT the occurrence of the character in the string T
        if c in self.dict_t and self.window[c] < self.dict_t[c]:
            self.missing += 1