Minimum Window Substring

Introduction to Minimum Window Substring

The Minimum Window Substring problem involves finding the smallest substring from a given string that contains all the characters of another string (referred to as the target string). This problem is particularly useful in various real-world applications, such as bioinformatics, searching engines, and text analysis.

Problem Statement

Given a string S and a target string T, the goal is to find the minimum window in S that contains all the characters of T. If no such window exists, we return an empty string.

Example

Let's clarify the problem with a simple example:

• Input: S = "ADOBECODEBANC"
• Target: T = "ABC"
• Output: "BANC"

In this case, the substring "BANC" is the smallest window that contains all the characters of "ABC".

Understanding the Approach

To solve the Minimum Window Substring problem efficiently, we can utilize a two-pointer technique combined with a hash map (or dictionary) to keep track of the counts of characters.

Steps to Approach:

1. Count Character Frequencies: Create a frequency map of characters present in the target string T.
2. Expand the Window: Use a right pointer to expand the window by iterating through the string S, keeping track of characters as you go.
3. Contract the Window: Once a potential window is found that includes all characters of T, move the left pointer to minimize the window while still containing all characters.
4. Update the Minimum Length: Whenever a valid window is found, check if it’s smaller than the previously recorded minimum and update accordingly.
5. Return the Result: After iterating through S, the smallest window coordinates can be used to extract the substring.

Implementation of the Solution

Here’s a Python implementation based on the above approach:

def min_window(s: str, t: str) -> str:
    from collections import Counter, defaultdict

# Base cases
    if not s or not t:
        return ""
    
    t_count = Counter(t)
    current_count = defaultdict(int)

    left, right = 0, 0
    required = len(t_count)
    formed = 0

    min_len = float('inf')
    min_left, min_right = 0, 0

    while right < len(s):
        char = s[right]
        current_count[char] += 1
        
        if char in t_count and current_count[char] == t_count[char]:
            formed += 1

        while left <= right and formed == required:
            char = s[left]

# Update minimum length and indices
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left, min_right = left, right

# Pop the leftmost character
            current_count[char] -= 1
            if char in t_count and current_count[char] < t_count[char]:
                formed -= 1
            
            left += 1
        
        right += 1
    
    return "" if min_len == float('inf') else s[min_left:min_right + 1]

Explanation of the Code

• We first check if either string S or T is empty and return an empty result accordingly.
• We create a frequency map for T using Counter which allows us to know how many characters we need to form a valid window.
• The current_count dictionary keeps track of the number of characters from S that we have in our current window.
• As we move the right pointer forward, we include characters and check if we have a valid window.
• Once we have a valid window, we use the left pointer to attempt to shrink the window until it no longer holds all characters from T.
• Finally, we return the minimum-length valid substring found.

Time and Space Complexity

• The time complexity of this approach is O(n + m), where n is the length of string S and m is the length of string T. This considers the linear traversal of both strings.
• The space complexity is O(m), which is required for the frequency counts of T.

By understanding this problem and its solution, you will be better equipped to handle similar challenges in string processing, making you more adept in interviews and real-world applications where efficient algorithms are critical.