76. Minimum Window Substring

Problem Description

The problem requires us to find the smallest segment (substring) from string s that contains all the characters from string t, including duplicates. This segment or substring must be minimized in length and must contain each character from t at least as many times as it appears in t. If we are unable to find such a segment, we should return an empty string. A key point is that the solution is guaranteed to be unique where applicable.

Intuition

To solve this problem, we employ a sliding window technique along with character counting. The main idea revolves around expanding and shrinking a window on string s to include the characters from t in the most efficient way possible.

Firstly, we need to know how many of each character from t need to be in our window. This is where need, our character count for t, comes into play.

We also keep a counter for the characters in our current window (window) and the number of characters from t in the window (cnt). Two pointers (i and j) mark the start and end of the current window. As we traverse s, we expand our window by including the current character and check if this character is "necessary" (meaning it's still required to meet the t character count criterion). If it is, we increment cnt.

Whenever cnt reaches the length of t, it means our window potentially includes all characters from t. At this point, we should attempt to shrink the window from the left by incrementing j, all the while making sure the window still contains all characters from t. If during this shrinkage we find a window smaller than our previous smallest (mi), we update our minimum window size (mi) and starting position (k).

The process of expanding and shrinking continues until the end of string s. If by the end we haven't found any such window, we return an empty string. Otherwise, we return the smallest window from s that contains all characters from t, starting at k with length mi.

Learn more about Sliding Window patterns.

Solution Approach

The solution utilizes a sliding window approach, which dynamically changes its size, along with two hash tables or counters to keep track of the characters in the sliding window (window) and the characters needed (need). The python Counter from the collections module has been used for this purpose as it conveniently allows counting the frequency of each character in strings s and t.

Here's the breakdown of the algorithm:

1. First, we initialize the need counter with the character frequencies of the string t since we want to find a substring of s that contains at least these many characters of t.

2. We also initialize a window counter with no characters, an integer cnt set to 0 to count the "necessary characters," indices j and k (j for the start of the sliding window and k for the start of the minimum window), and a variable mi representing the minimum length infinity (inf provided by python) of the window.

3. We then iterate over the string s with the index i and character c, expanding the window by adding the character c.

4. If the character c is "necessary," meaning need[c] >= window[c] (it contributes to forming a window that covers t), we increment cnt.

5. A while loop starts whenever cnt matches the length of t, indicating that our current window has all the characters needed in string t. Inside this loop:

   • We check if the current window size (i - j + 1) is smaller than the previously recorded minimum (mi). If it is, we update mi with the new window size and k with the new start position of the window (j).
   • Shrink the window from the left by moving j right. If the character s[j] at the left boundary was "necessary," decrement cnt. Given we are potentially removing a "necessary character," we update the window count for that character.
   • Continue to move j to the right as long as cnt equals the length of t and the condition need[s[j]] >= window[s[j]] holds true.

6. After the loop ends, if cnt does not equal the length of t, it means our current window is missing some characters from t, and we expand the window by moving i to the right, otherwise, we continue to shrink the window.

7. Once we've traversed all of s, we check if we found a minimum window (by checking if k>=0). If we have, we return the substring s[k:k + mi], otherwise, we return an empty string as per the problem's requirement.

This approach ensures that all characters of t are included in the minimum window in s as efficiently as possible, by appropriately expanding and shrinking the size of the window.

Example Walkthrough

Let's take a small example to illustrate the solution approach. Suppose s = "ADOBECODEBANC" and t = "ABC".

1. We initialize need with the frequencies of character of t: need = {'A': 1, 'B': 1, 'C': 1}.

2. Initialize window as an empty counter, cnt as 0, j and k both to 0, and mi as infinity.

3. We start iterating over s with our i pointer starting from the 0th index.

4. When i = 0, c = A, we found a necessary character A. We update window to {'A': 1} and increment cnt to 1.

5. At i = 3, c = B, window becomes {'A': 1, 'B': 1} and cnt now is 2.

6. At i = 5, c = C, window updates to {'A': 1, 'B': 1, 'C': 1} and cnt increases to 3, which is the length of t. Now we have a potential window "ADOBEC" from index 0 to 5.

7. Since cnt equals the length of t, we enter the while loop and notice the current window size is smaller than mi (infinity), so we update mi = 6, and k = 0.

8. Next, we move j right to shrink the window while checking if it still contains t fully. The window now can be shrunk because it contains extra characters not needed.

9. When j = 3, s[j] = B, which is necessary, we decrement window['B'] and, since need['B'] is still greater, decrement cnt.

10. We exit the while loop because the window is not valid (no longer contains all of t), cnt is no longer equal to the length of t.

11. We continue with the expansion of the window by moving i to the right.

12. At i = 9, cnt again matches the length of t, indicating another potential window "BECODEBA".

13. Entering the while loop, we successfully shrink this window to "CODEBA" and then to "ODEBA" and finally to "DEBA" before it becomes invalid as cnt drops below the length of t.

14. We continue this process of expansion and shrinkage until we reach the end of s.

15. At the end of traversal, we have a mi of 4 and a k of 9, which corresponds to the window "BANC" which is the smallest window containing all characters of t.

16. We then return this window s[9:9+4] which equals "BANC".

By following this approach using the sliding window technique and character counting, we efficiently find the smallest segment in s that contains all the characters of t.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code is O(m + n). This is because the code iterates through all characters of string s once which is of length m, and for each character, it performs a constant number of operations. Additionally, it iterates through the characters of string t once which is of length n to fill the need Counter object. The while loop and the inner operations are also constant time because it will at most iterate for every character in string s. Altogether, this gives us two linear traversals resulting in O(2m + n), which simplifies to O(m + n).

The space complexity of the code is O(C), where C is the fixed size of the character set. In the code, we have two Counter objects: need and window. Since the Counter objects will only have as many entries as there are unique characters in strings s and t, and given that the size of the character set is fixed at 128, the space used by these counters does not depend on the size of the input strings themselves but on the size of the character set, making it O(C).

Learn more about how to find time and space complexity quickly using problem constraints.