Minimum Window Substring - Python Solution

1. Introduction

The "Minimum Window Substring" problem is a notable example of the sliding window technique in string manipulation. It involves finding the smallest substring in one string that contains all the characters of another string, including duplicates. This problem is often used to test understanding of string processing and efficient searching techniques.

Problem

Given two strings s and t, where s is the source string and t is the target string, the task is to find the minimum window substring in s which contains all characters of t (including duplicates). If no such substring exists, return an empty string. The solution must handle varying lengths of s and t.

2. Solution Steps

1. Create a hash table (dictionary) to store the count of each character in t.

2. Use two pointers to create a sliding window on s.

3. Expand the window by moving the right pointer until it includes all characters of t.

4. Contract the window by moving the left pointer to find a smaller window that still contains all characters of t.

5. Keep track of the minimum window size and its starting index.

6. Repeat steps 3 and 4 until the right pointer reaches the end of s.

7. Return the minimum window substring found, or an empty string if no such window exists.

3. Code Program

def minWindow(s, t):
    if not t or not s:
        return ""

    dict_t = Counter(t)
    required = len(dict_t)
    l, r = 0, 0
    formed = 0
    window_counts = {}
    ans = float("inf"), None, None

    while r < len(s):
        character = s[r]
        window_counts[character] = window_counts.get(character, 0) + 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
print(minWindow("ADOBECODEBANC", "ABC"))  # Output: "BANC"
print(minWindow("a", "a"))                # Output: "a"
print(minWindow("a", "aa"))               # Output: ""

Output:

"BANC"
"a"
""

Explanation:

1. Character Frequency: The count of each character in t is stored in a hash table.

2. Sliding Window Technique: Two pointers are used to create a dynamic window in s.

3. Expanding Window: The right pointer expands the window to include necessary characters.

4. Contracting Window: The left pointer contracts the window to find the minimum length.

5. Tracking Minimum Window: The size and indices of the smallest valid window are tracked.

6. Result Calculation: The substring corresponding to the minimum window is returned.

7. Edge Cases: Handles cases where no valid window is found by returning an empty string.