76. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window 

 of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

 

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

The following python code can be used to find the minimum window substring in the given string s that includes the characters in string t.

# this function is to find the minimum window substring in the given string s that includes the characters in string t
def min_window_substring(s: str, t: str) -> str:
    
    # if the length of string t is greater than the length of string s, then return empty string
    if len(t) > len(s):
        return ""
    
    # dictionary to store the count of characters in string t
    t_count = {}
    # storing the count of characters in string t in the dictionary
    for ch in t:
        t_count[ch] = t_count.get(ch, 0) + 1
    
    # variable to store the number of unique characters in string t
    unique_characters = len(t_count)
    # variable to store the left index of the minimum window substring
    left = 0
    # variable to store the right index of the minimum window substring
    right = 0
    # variable to store the length of the minimum window substring
    window_length = float('inf')
    # variable to store the starting index of the minimum window substring
    start = 0
    # dictionary to store the count of characters in the current window
    window_count = {}
    
    # loop through all the characters in string s
    while right < len(s):
        
        # get the current character
        ch = s[right]
        # add the count of the current character in the window_count dictionary
        window_count[ch] = window_count.get(ch, 0) + 1
        
        # if the count of the current character in the window_count dictionary is same as the count of that character in the t_count dictionary,
        # then decrement the value of the unique_characters variable by 1
        if ch in t_count and window_count[ch] == t_count[ch]:
            unique_characters -= 1
        
        # if all the characters of string t is present in the current window,
        # then move the left pointer to the right until the count of the current character in the window_count dictionary is not same as the count of that character in the t_count dictionary
        while unique_characters == 0:
            
            # if the length of the current window is less than the minimum window length,
            # then update the minimum window length and the starting index of the minimum window
            if right - left + 1 < window_length:
                window_length = right - left + 1
                start = left
            
            # get the character at the left pointer
            ch = s[left]
            # decrement the count of the character at the left pointer in the window_count dictionary by 1
            window_count[ch] -= 1
            # if the count of the character at the left pointer in the window_count dictionary is less than the count of that character in the t_count dictionary,
            # then increment the value of the unique_characters variable by 1
            if ch in t_count and window_count[ch] < t_count[ch]:
                unique_characters += 1
            # increment the value of the left pointer by 1
            left += 1
        
        # increment the value of the right pointer by 1


Explanation:

This code is used to find the minimum window substring in the given string s that includes the characters in the string t.

The min_window_substring function takes two strings, s and t, as input and returns the minimum window substring of s that includes all the characters in t. If there is no such substring, it returns the empty string "".

First, the function checks if the length of string t is greater than the length of string s. If this is the case, then it returns an empty string. This is because it is not possible to find a window substring in s that includes all the characters in t if the length of t is greater than the length of s.

Then, the function creates a dictionary, t_count, to store the count of each character in string t. It loops through all the characters in t and increments the count of each character in the t_count dictionary.

Next, the function initializes the unique_characters variable with the number of unique characters in string t. This is used to keep track of the number of unique characters in the current window. The left and right variables are used to store the left and right indices of the minimum window substring, respectively. The window_length variable is used to store the length of the minimum window substring. The start variable is used to store the starting index of the minimum window substring. Finally, the function creates a dictionary, window_count, to store the count of each character in the current window.

The function then loops through all the characters in string s and moves the right pointer to the right by one position at each iteration.

At each iteration, the function gets the current character, adds its count to the window_count dictionary, and checks if the count of the current character in the window_count dictionary is the same as the count of that character in the t_count dictionary. If this is the case, then the function decrements the value of the unique_characters variable by one.

Next, the function checks if all the characters of string t are present in the current window. If this is the case, then it moves the left pointer to the right until the count of the current character in the window_count dictionary is not the same as the count of that character in the t_count dictionary. At each iteration, the function checks if the length of the current window is less than the minimum window length. If this is the case, then it updates the minimum window length and the starting index of the minimum window.

Finally, the function returns the minimum window substring.