Here’s a solution to the “Minimum Window Substring” problem:

from collections import Counter

def min_window_substring(s: str, t: str) -> str:
    # Check if the length of s is less than the length of t
    if len(s) < len(t):
        return ""

    # Initialize variables to track the minimum window
    min_len = float('inf')
    min_window = ""
    
    # Create counters for characters in t and the current window
    char_count_t = Counter(t)
    char_count_window = Counter()

    # Initialize pointers for the start and end of the window
    start = 0
    end = 0

    # Variable to track the number of characters from t in the current window
    required_chars = len(char_count_t)

    # Variable to track the number of characters from t found in the current window
    found_chars = 0

    # Iterate through the string s using the end pointer
    while end < len(s):
        # Update char_count_window with the current character
        char_count_window[s[end]] += 1

        # Check if the current character is part of t and its count matches in both counters
        if s[end] in char_count_t and char_count_window[s[end]] == char_count_t[s[end]]:
            found_chars += 1

        # Try to minimize the window by moving the start pointer
        while start <= end and found_chars == required_chars:
            # Update the minimum window if the current window is smaller
            if end - start + 1 < min_len:
                min_len = end - start + 1
                min_window = s[start:end + 1]

            # Move the start pointer and update char_count_window accordingly
            char_count_window[s[start]] -= 1
            if s[start] in char_count_t and char_count_window[s[start]] < char_count_t[s[start]]:
                found_chars -= 1

            start += 1

        # Move the end pointer to explore more characters in s
        end += 1

    return min_window

# Example usage:
result = min_window_substring("ab", "a")
print(result)
assert result == "a"

result = min_window_substring("abccb", "cc")
print(result)
assert result == "cc"

result = min_window_substring("ADOBXBCODEBANC", "ABC")
print(result)
assert result == "BANC"

result = min_window_substring("x", "a")
print(result)
assert result == ""

result = min_window_substring("a", "aa")
print(result)
assert result == ""

Time Complexity:

The time complexity of the solution is O(S + T), where S is the length of string s, and T is the length of string t. Let’s break down the major components contributing to this time complexity:

  1. Iteration through String s and String t:
    • The algorithm uses two pointers, start and end, to iterate through each character of string s. The end pointer moves through the entire length of s, contributing O(S) to the time complexity.
    • The algorithm also iterates through each character of string t to build the character count, contributing O(T) to the time complexity.
  2. Sliding Window Technique:
    • The sliding window technique involves moving the start and end pointers to explore substrings within s. In the worst case, each character in s is processed twice (once by the end pointer and once by the start pointer). This contributes O(S) to the time complexity.
  3. Character Count Updates:
    • When updating the character counts for the current window, the algorithm increments or decrements counts for characters. These operations are constant time for each character, and the worst-case number of operations is proportional to the length of s.
  4. Comparisons and Checks:
    • The algorithm performs comparisons between character counts and checks whether the current window contains all the required characters from t. These operations are constant time for each character, and the worst-case number of operations is proportional to the length of s.

Combining these factors, the overall time complexity is O(S + T). The linear dependence on both the lengths of s and t indicates that the algorithm’s performance scales linearly with the input sizes of both strings.

Space Complexity:

The space complexity of the solution is O(S + T), where S is the length of string s, and T is the length of string t. Let’s break down the major components contributing to this space complexity:

  1. Character Count Dictionaries:
    • The algorithm uses two dictionaries, char_count_t and char_count_window, to store the character counts of string t and the current window in string s, respectively. The size of these dictionaries depends on the unique characters in t and the characters within the current window. In the worst case, both dictionaries could contain all distinct characters from s and t, contributing O(S + T) to the space complexity.
  2. Pointers and Counters:
    • The algorithm uses pointers (start and end) and counters (found_chars, required_chars) to keep track of the current state while iterating through the strings. These variables have constant space requirements and do not depend on the input sizes.

Combining these factors, the overall space complexity is O(S + T). The linear dependence on both the lengths of s and t indicates that the algorithm’s space usage scales linearly with the input sizes of both strings. The dominant factor is the space required for storing character counts in dictionaries.