Sliding Window: Minimum Window Substring

Question:

Given two strings s and t, return the minimum window substring of s that contains all the characters of t. If there is no such substring, return an empty string.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "a", t = "a"
Output: "a"

Answer:

To solve this problem, we can use the sliding window technique. The basic idea is to use two pointers: left and right, to represent the current window. We move the right pointer to expand the window and move the left pointer to shrink the window.

Here is the step-by-step algorithm to solve this problem:

1. Create two hash maps desiredCounts and actualCounts to store the count of each character in t and current window of s respectively.

2. Initialize the left and right pointers to the start of the string s, and initialize the matched variable to 0 to keep track of the number of characters in t that are present in the current window.

3. Iterate right pointer until the end of the string s:

   • If the character at the right pointer is present in t, we increment the count in actualCounts hash map. If this count is equal to or less than the count in desiredCounts, we increment the matched variable.
   • If matched is equal to the length of t, it means we have found a window that contains all the characters of t. We can consider shrinking the window from the left to find the minimum window substring.
   • If the character at the left pointer is present in t, we decrement the count in actualCounts hash map. If this count is less than the count in desiredCounts, we decrement the matched variable.
   • Calculate the length of the current window by right - left + 1. If the length is less than the length of the minimum window substring found so far, update it.
   • Move the left pointer one step to the right to shrink the window.

4. Return the minimum window substring found.

Here is the implementation of the above approach in Python:

def minWindow(s, t):
    if not s or not t or len(s) < len(t):
        return ""
    
    desiredCounts = {}
    actualCounts = {}
    for ch in t:
        desiredCounts[ch] = desiredCounts.get(ch, 0) + 1
    
    left = right = matched = 0
    minLen = float('inf')
    minStart = 0
    
    while right < len(s):
        if s[right] in desiredCounts:
            actualCounts[s[right]] = actualCounts.get(s[right], 0) + 1
            if actualCounts[s[right]] <= desiredCounts[s[right]]:
                matched += 1
        
        while matched == len(t):
            if right - left + 1 < minLen:
                minLen = right - left + 1
                minStart = left
            
            if s[left] in desiredCounts:
                actualCounts[s[left]] -= 1
                if actualCounts[s[left]] < desiredCounts[s[left]]:
                    matched -= 1
            
            left += 1
        
        right += 1
    
    if minLen == float('inf'):
        return ""
    
    return s[minStart:minStart+minLen]

The time complexity of this algorithm is O(n), where n is the length of the string s. This is because at most each character in s will be visit twice (once by the right pointer and once by the left pointer). The space complexity is O(m), where m is the length of the string t since we are using hash maps to store the counts of characters.