Minimum Window Substring hard

Problem Statement

Given two strings s and t, find 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 "". Note that if there are multiple minimum-window substrings, you can return any of them.

Example 1

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2

Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.

Steps

1. Character Counts: Create a dictionary t_count to store the frequency of each character in string t.

2. Sliding Window: Use a sliding window approach with two pointers, left and right, initially at the beginning of string s.

3. Window Maintenance: As the right pointer moves, update a dictionary window_count to track the frequency of characters within the current window.

4. Check for Match: Compare window_count with t_count. If all characters in t are present in the current window (with at least the required frequency), we have a potential minimum window.

5. Shrink Window: Once a valid window is found, try to shrink the window from the left (left pointer) while maintaining the condition that all characters in t are still present. This helps find the minimum window.

6. Update Minimum Window: Keep track of the minimum window found so far.

7. Continue Expansion: Continue expanding the window (moving the right pointer) until the right pointer reaches the end of string s.

Explanation

The solution uses a sliding window technique, which is efficient for finding sub-arrays or sub-strings that satisfy certain conditions. The key is to efficiently track the characters within the window and determine when a valid window (containing all characters from t) is found. Shrinking the window from the left helps to minimize its size. The use of dictionaries for character counts simplifies the process of comparing character frequencies.

Code

from collections import Counter

def minWindow(s, t):
    """
    Finds the minimum window substring in s containing all characters from t.

    Args:
        s: The main string.
        t: The string containing characters to search for.

    Returns:
        The minimum window substring, or "" if not found.
    """

    if not t or not s:
        return ""

    t_count = Counter(t)  # Count character frequencies in t
    required = len(t_count)  # Number of unique characters in t

    window_count = {}  # Count characters in the current window
    formed = 0  # Number of unique characters in t present in the window

    left, right = 0, 0
    min_window = ""
    min_window_len = float('inf')

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

        if char in t_count and window_count[char] == t_count[char]:
            formed += 1

        while left <= right and formed == required:
            char = s[left]
            window_length = right - left + 1

            if window_length < min_window_len:
                min_window_len = window_length
                min_window = s[left:right+1]

            window_count[char] -= 1
            if char in t_count and window_count[char] < t_count[char]:
                formed -= 1

            left += 1
        right += 1

    return min_window

Complexity

• Time Complexity: O(S), where S is the length of string s. The right pointer iterates through the entire string once. The left pointer also moves at most the length of s.
• Space Complexity: O(1). The dictionaries t_count and window_count have a maximum size bounded by the number of unique characters in the alphabet (typically 26 for lowercase English letters), which is constant.