Minimum Window Substring

December 27, 2023

Problem #

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string.

Solution #

The Python function min_window successfully finds the minimum window in the string s that contains all the characters of the string t. In the provided example with s = "ADOBECODEBANC" and t = "ABC", the function returned "BANC" as the smallest substring of s that includes all the characters in t.

Here’s the code for the min_window function:

def min_window(s, t):
    """
    Find the minimum window in s which will contain all the characters in t.
    If no such window exists, return an empty string.

    :param s: Source string
    :param t: Target string
    :return: Minimum window substring or empty string
    """
    if not t or not s:
        return ""

    dict_t = collections.Counter(t)

    required = len(dict_t)

    l, r = 0, 0
    formed = 0
    window_counts = collections.Counter()
    ans = float("inf"), None, None

    while r < len(s):
        character = s[r]
        window_counts[character] += 1

        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1

        while l <= r and formed == required:
            character = s[l]
            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)

            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1

            l += 1    

        r += 1    
    return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]

# Example usage
s = "ADOBECODEBANC"
t = "ABC"
min_window(s, t)

This function works by using a sliding window technique to find the smallest substring in s that contains all the characters of t. It expands the window by moving the right pointer and shrinks it by moving the left pointer while keeping track of the number of required characters that are currently in the window. When the window fulfills the requirement (contains all characters from t), it updates the answer with the minimum window size found so far.

Solution Analysis #

The min_window function is designed to find the smallest substring in a given string s that contains all the characters of another string t. It uses the sliding window technique, a common approach for solving substring search problems. Let’s break down the code into its main components:

1. Initial Checks and Setup #

• The function first checks if either s or t is empty. If so, it returns an empty string, as there can be no valid window.
• dict_t is a dictionary that stores the count of each character in t. This helps to keep track of what characters and how many of each we need to find in s.
• required is the number of unique characters in t that we need to find in s.

2. Sliding Window Initialization #

• Two pointers, l (left) and r (right), are initialized to 0. They represent the bounds of the sliding window.
• formed keeps track of how many unique characters from t have been found in the current window in the correct frequency.
• window_counts is a dictionary to store the count of each character in the current window.
• ans is a tuple that will eventually store the length of the minimum window, and the left and right indices of this window in s.

3. Sliding Window Expansion #

• The outer while loop (controlled by r < len(s)) is used to expand the window by moving the right pointer r. For each character added to the window, its count is updated in window_counts.
• If a character from s is also in t and its count matches the required count in t, formed is incremented.

4. Sliding Window Contraction #

• The inner while loop is executed when formed equals required, meaning the current window contains all the necessary characters from t.
• Inside this loop, the function checks if the current window length is smaller than the smallest found so far. If it is, it updates ans with the new window length and indices.
• Then, the function attempts to contract the window by increasing the left pointer l and adjusting the counts in window_counts. If the window no longer contains all characters from t in the required frequency, formed is decremented.

5. Result #

• The function returns the smallest window found. If no such window is found (ans[0] remains float("inf")), an empty string is returned.

Example Usage #

• The example uses s = "ADOBECODEBANC" and t = "ABC". The function finds “BANC” as the smallest substring of s containing all characters of t.

This code is efficient for substring search problems, as it dynamically adjusts the window size and only iterates through the string s once, achieving good time complexity.