Leetcode 76. Minimum Window Substring

Problem Explanation:

The problem, is to find a minimum window in the string S which contains all characters present in the string T. The solutions to this problem should have a complexity of O(n). If no such window can be found in string S, we return an empty string "".

To further elaborate, let's take an example. Suppose we have string S = "ADOBECODEBANC" and string T = "ABC", we are to find the smallest substring from S which has all the characters in T. In this case, the substring would be "BANC" as it contains A, B, and C.

Approach to the solution:

The solution uses a sliding window approach. We first traverse the T string and increment the count of each character in a count array. We then traverse the S string. Whenever we encounter a character of T (we decrease the count of character and decrease the required count), we try to minimise the window by moving a pointer from the start, until the condition that all characters of T are still present in the window (i.e. required == 0). We keep track of the smallest window seen so far.

Python Solution:

1
2python
3
4class Solution:
5    def minWindow(self, s: str, t: str) -> str:
6        from collections import Counter
7        t_counter = Counter(t)
8        required = len(t_counter)
9        l, r = 0, 0
10        formed = 0  
11        window_counts = {}
12        ans = float("inf"), None, None
13        while r < len(s):
14            character = s[r]
15            window_counts[character] = window_counts.get(character, 0) + 1
16            if character in t_counter and window_counts[character] == t_counter[character]:
17                formed += 1
18            while l <= r and formed == required:
19                character = s[l]
20                if r - l + 1 < ans[0]:
21                    ans = (r - l + 1, l, r)
22                window_counts[character] -= 1
23                if character in t_counter and window_counts[character] < t_counter[character]:
24                    formed -= 1
25                l += 1    
26            r += 1        
27        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]

Java Solution:

1
2java
3
4class Solution {
5    public String minWindow(String s, String t) {
6        int[] count = new int[128];
7        int required = t.length();
8        int left = 0, right = 0;
9        int minLength = s.length() + 1;
10        int bestLeft = -1;
11        for (char c : t.toCharArray()) {
12            ++count[c];
13        }
14        while (right < s.length()) {
15            if (--count[s.charAt(right++)] >= 0)
16                --required;
17            while (required == 0) {
18                if (right - left < minLength) {
19                    minLength = right - left;
20                    bestLeft = left;
21                }
22                if (++count[s.charAt(left++)] > 0)
23                    ++required;
24            }
25        }
26        return bestLeft == -1 ? "" : s.substring(bestLeft, bestLeft + minLength);
27    }
28}

JavaScript Solution:

1
2javascript
3
4var minWindow = function(s, t) {
5    let ans = '';
6    let tracker = Array(128).fill(0);
7    let left = 0, right = 0;
8    let min = Infinity;
9    let count = t.length;
10    
11    for(let c of t) {
12        tracker[c.charCodeAt() - 'A'.charCodeAt()]++;
13    }
14    
15    while(right < s.length) {
16        if(tracker[s.charCodeAt(right++) - 'A'.charCodeAt()]-- > 0) count--;
17        while(count === 0) {
18            if(right - left < min) {
19                min = right - left;
20                ans = s.substr(left, min);
21            }
22            if(tracker[s.charCodeAt(left++) - 'A'.charCodeAt()]++ === 0) count++;
23        }
24    }
25    
26    return ans;
27};
28

In the JavaScript solution provided, we first initialize an empty string ans that will hold our answer. We also create a tracker array of size 128 filled with 0s, which will keep track of the occurrence of the characters of the string T in the string S. We also have two pointers, left and right.

We then navigate the string T incrementing the counts of its characters in the tracker array. After this, a while loop navigates the string S. The right pointer is increased first, if the character at the current right pointer in the string S is a character in the string T, we decrement its count in the tracker.

The inner while loop is executed when all characters from the string T are found in the substrings of string S (i.e., count is 0). In this while loop, we check if the length of the substring is less than the minimum length found up until now. If it is, we update the minimum length and set our answer to the current substring. We then increment our left pointer.

When the substring no longer contains all characters of string T, we increment the count and exit the inner while loop, and the process continues until all substrings have been checked.

In the end, we return our answer. This solution also uses the sliding window approach, efficiently solving the problem in linear time.