Minimum Window Substring

Problem Statement: Given two strings s and t, find the minimum-length substring of s that contains all the characters of t (including duplicates). If no such substring exists, return an empty string.

Approach: This problem is efficiently solved using a sliding window technique combined with a frequency counter.

Algorithm:

1. Frequency Counts: Create two frequency maps (dictionaries or arrays):

   • need: Stores the frequency of each character in string t.
   • window: Stores the frequency of characters currently within the sliding window in s.

2. Sliding Window: Initialize two pointers, left and right, both starting at index 0. right will expand the window, while left will contract it.

3. Window Expansion: Move right to the right, adding each character to the window frequency map.

4. Valid Window Check: Check if the window contains all the characters from t with at least the required frequencies (as specified in need). This is done by comparing window[char] >= need[char] for every character in t. A counter valid can track how many characters in need are satisfied by window.

5. Window Contraction: If the window is valid, try to shrink the window from the left (left pointer). If shrinking the window still maintains a valid window, this optimizes for the smallest possible valid substring. This step is crucial for efficiency.

6. Update Minimum Window: If a valid window is found, update the min_len and the start index (min_start) of the minimum window.

7. Repeat: Continue expanding (right) and contracting (left) until the right pointer reaches the end of s.

Time and Space Complexity:

• Time Complexity: O(m + n), where 'm' is the length of s and 'n' is the length of `t'. The pointers traverse each string once.
• Space Complexity: O(k), where 'k' is the number of unique characters. This is due to the frequency maps.

Code Implementation (Python):

from collections import defaultdict
 
def minWindow(s, t):
    if not t or not s:
        return ""
 
    need = defaultdict(int)
    for c in t:
        need[c] += 1
 
    window = defaultdict(int)
    left, right = 0, 0
    valid = 0  # Count of characters in window that meet need
    min_len = float('inf')
    min_start = -1
 
    while right < len(s):
        c = s[right]
        right += 1
        if c in need:  # Only care about characters in t
            window[c] += 1
            if window[c] == need[c]:
                valid += 1
 
        while valid == len(need):  # Window contains all characters from t
            # Update minimum window if necessary
            if right - left < min_len:
                min_len = right - left
                min_start = left
            
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
    
    return "" if min_start == -1 else s[min_start:min_start + min_len]
 
 
# Example usage
s = "ADOBECODEBANC"
t = "ABC"
print(minWindow(s, t))  # Output: "BANC"
 
s = "a"
t = "a"
print(minWindow(s,t)) # Output: "a"
 
s = "a"
t = "aa"
print(minWindow(s,t)) # Output: ""

Code Implementation (Other Languages): The approach remains the same; only the syntax and data structure implementations will vary. For example, in Java or C++, you might use HashMap or arrays for frequency counting. The core logic of the sliding window and the validity check would stay consistent.