Minimum Window Substring Problem

Given two strings s and t, the goal is to find the minimum window substring of s that contains all characters of t (including duplicates).

1. Brute Force Solution

A naive approach involves generating all possible substrings of s and checking if each substring contains all characters of t. This approach is highly inefficient.

Algorithm:

1. Generate all substrings of s.
2. For each substring, check if it contains all characters of t.
3. If it does, compare its length with the current minimum window. Update the minimum window if the current substring is smaller.

Code (Python):

def min_window_brute_force(s, t):
    if not s or not t or len(s) < len(t):
        return ""

    min_window = ""

    for i in range(len(s)):
        for j in range(i, len(s)):
            substring = s[i:j+1]
            if contains_all(substring, t):
                if not min_window or len(substring) < len(min_window):
                    min_window = substring

    return min_window

def contains_all(s, t):
    t_freq = {}
    for char in t:
        t_freq[char] = t_freq.get(char, 0) + 1

    s_freq = {}
    for char in s:
        s_freq[char] = s_freq.get(char, 0) + 1

    for char, freq in t_freq.items():
        if char not in s_freq or s_freq[char] < freq:
            return False

    return True

Time Complexity:

• O(n³), where n is the length of string s. Generating all substrings takes O(n²) time, and checking each substring takes O(n) time in the worst case.

Space Complexity:

• O(n), where n is the length of string s, to store the substring.

2. Optimal Solution: Sliding Window

A more efficient approach uses the sliding window technique.

Algorithm:

1. Create two frequency maps: one for string t and another for the current window in s.
2. Use two pointers, left and right, to maintain the sliding window.
3. Move the right pointer to expand the window until it contains all characters of t.
4. Once the window contains all characters of t, move the left pointer to shrink the window while still maintaining all characters of t.
5. Keep track of the minimum window found so far.

Code (Python):

def min_window(s, t):
    if not s or not t or len(s) < len(t):
        return ""

    t_freq = {}
    for char in t:
        t_freq[char] = t_freq.get(char, 0) + 1

    required = len(t_freq)
    formed = 0
    window_freq = {}

    left = 0
    right = 0

    min_length = float('inf')
    min_window = ""

    while right < len(s):
        char = s[right]
        window_freq[char] = window_freq.get(char, 0) + 1

        if char in t_freq and window_freq[char] == t_freq[char]:
            formed += 1

        while formed == required:
            if right - left + 1 < min_length:
                min_length = right - left + 1
                min_window = s[left:right+1]

            char = s[left]
            window_freq[char] -= 1

            if char in t_freq and window_freq[char] < t_freq[char]:
                formed -= 1

            left += 1

        right += 1

    return min_window

Time Complexity:

• O(m + n), where m is the length of string s and n is the length of string t. The right and left pointers each traverse the string s at most once. Building the frequency maps takes O(n) time.

Space Complexity:

• O(m + n) in the worst case. The space is used to store the frequency maps for string t and the current window in s. In the worst case, all characters in s and t are unique.

3. Edge Cases

• Empty strings: If either s or t is empty, or if the length of s is less than the length of t, return an empty string.
• t contains characters not in s: If s does not contain all the characters in t, return an empty string.
• t has duplicate characters that are not present in s in the same count`: Return an empty string. For example, s = "a", t = "aa".
• s = a, t = a: return a
• No valid substring: If no substring of s contains all characters of t, return an empty string.