Minimum Window Substring

Write a function minWindowSubstring that takes two strings s and t. The function should return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such window exists, return an empty string. The order of the characters in the target string t does not need to match the order in the window.

Constraints

The length of string s and t will be between 1 and 10,000.
The strings will consist of English alphabetic characters and are case sensitive.

Examples

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window in s that contains every character in t is "BANC".

Input: s = "a", t = "a"
Output: "a"
Explanation: The minimum window in s that contains t is "a" itself.

Tips:

  • Consider using two pointers to create a sliding window over s.
  • Use a hash map to keep track of the characters and their counts in t.
  • Expand and contract the window while updating a hash map for the window to find the minimum length substring that contains all characters of t.

Solution

What’s the Exact Minimum Window Substring Problem?

The problem is to find the smallest substring in s that contains all the characters in t, including duplicates.

Steps to Understand the Minimum Window Substring Problem

Understand that you need to find a substring in s where all characters in t are present.
The order of characters from t in the substring doesn’t matter.
The challenge lies in optimizing the search to find the minimum length substring.

Examples

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Input: s = "a", t = "a"
Output: "a"

What Your Function Should Do?

The function minWindowSubstring should take two strings s and t and return the minimum window substring of s that contains every character of t.

How to Solve the Minimum Window Substring Problem

  • Use the sliding window technique with two pointers to traverse through s.
  • Utilize a hash map to count the characters of t and another hash map to count characters in the current window of s.
  • Expand and contract the window and update the counts in the hash map to find the minimum length substring that contains all characters of t.

Example Code Solution

from collections import Counter

def minWindowSubstring(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(minWindowSubstring("ADOBECODEBANC", "ABC"))  # Output: "BANC"
print(minWindowSubstring("a", "a"))                # Output: "a"

How this Code Works:

  • The function uses two pointers (l and r) to create a sliding window over s.
  • It uses two hash maps: dict_t for the count of each character in t and window_counts for the count of each character in the current window of s.
  • The window is expanded by moving r and updated window_counts accordingly. When all characters from t are found in the window, the function tries to contract the window by moving l to find the minimum length substring.
  • The ans tuple keeps track of the length and starting and ending indices of the minimum window found.

Time Complexity

The time complexity of this solution is O(S + T), where S is the length of string s and T is the length of string t. This is because the function iterates through each character of s and t at most twice - once by the right pointer and once by the left pointer. The space complexity is O(S + T) for the hash maps used to store character counts.