Minimum Window Substring - Leetcode Solution

The Minimum Window Substring problem is a famous problem on LeetCode that requires you to find the smallest window in a string that contains all the characters of another string. This problem can be solved using a sliding window technique and hashing.

Here is a detailed solution on how to solve the Minimum Window Substring problem on LeetCode:

Step 1: Initialize two hash tables

• One hash table will store the frequency of each character in target string.
• The other hash table will store the frequency of each character in the sliding window.

Step 2: Determine the length of the target string.

• This step is important as we will use it later to check if we have found the minimum substring.

Step 3: Traverse the string.

• For each character, update the frequency of that character in the sliding window hash table.
• Check if the current sliding window contains all the characters of the target string.
• If yes, move the start index of the sliding window until we have the minimum window that contains all the characters of the target string.
• If no, continue to slide the window and update the frequency of characters until we find a window that contains all the characters.

Step 4: Return the minimum window.

• If a minimum window is found, return it. Otherwise, return an empty string.

Here is the Python implementation of the above algorithm:

def minWindow(s, t):
    target = {}
    window = {}
    
    for ch in t:
        target[ch] = target.get(ch, 0) + 1
        
    left, correct, right, result = 0, 0, 0, ""
    while right<len(s):
        ch = s[right]
        if ch in target:
            window[ch] = window.get(ch, 0) + 1
            if window[ch] == target[ch]:
                correct += 1
                
        while correct == len(target):
            if not result or right-left+1<len(result):
                result = s[left:right+1]
            ch = s[left]
            if ch in target:
                window[ch] -= 1
                if window[ch] < target[ch]:
                    correct -= 1
            left += 1
        
        right += 1
        
    return result

In the above implementation, we first initialize two hash tables for target and window and then calculate the length of target. We then traverse the string and update the frequency of characters in the window hash table and check if we have found all the characters of the target string. If we have found all characters, we move the start index of the window until we have found the minimum window. Finally, we return the minimum window that contains all the characters of the target string.

1