Problem Statement

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The test cases will be generated such that the answer is unique.

Additional information

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

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"

Example 3:

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

Output: ""

Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.

Brute Force

Intuition
The simplest approach is to check every possible substring of s to see if it contains all characters from t. We can generate all substrings using two loops and, for each substring, compare its character counts with t. We keep track of the shortest valid substring found.

Algorithm

1. If t is empty, return "".
2. Initialize min_len to infinity and res to "".
3. Iterate i from 0 to len(s).
4. Iterate j from i to len(s).
5. Extract substring sub = s[i : j+1].
6. Check if sub contains all characters of t with correct frequencies.
7. If valid and len(sub) < min_len, update res and min_len.
8. Return res.

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not t or not s:
        return ""
    
    t_count = Counter(t)
    min_len = float("inf")
    res = ""
    
    for i in range(len(s)):
        for j in range(i, len(s)):
            sub = s[i : j + 1]
            sub_count = Counter(sub)
            
            # Check if valid
            valid = True
            for char in t_count:
                if sub_count[char] < t_count[char]:
                    valid = False
                    break
            
            if valid:
                if len(sub) < min_len:
                    min_len = len(sub)
                    res = sub
                    
    return res

Time & Space Complexity

• Time complexity: O(n^3)

• Reason: Generating substrings is O(n^2), and checking validity takes O(m) or O(n).

• Space complexity: O(m)

• Reason: Storing character counts.

Sliding Window (Optimal)

Intuition
We can use a sliding window with two pointers, l (left) and r (right).

1. Expand: Move r to the right to include characters. When the window contains all characters from t, it becomes "valid".
2. Contract: Once valid, try to shrink the window from the left (l) to make it smaller while maintaining validity. This helps us find the minimum length.
3. To do this efficiently, instead of comparing full Hash Maps every time, we maintain a count of how many unique characters currently satisfy the requirement (have) versus how many we need (need).

Algorithm

1. Create a frequency map countT for string t.
2. Initialize window map for the current window.
3. Set have = 0 and need = len(countT).
4. Initialize res pointers res_len (infinity) and res range [-1, -1].
5. Iterate r through s.

• Add s[r] to window.
• If s[r] is in countT and window[s[r]] == countT[s[r]], increment have.
• **While have == need** (Window is valid):
• Update result if current window (r - l + 1) is smaller than res_len.
• Remove s[l] from window.
• If s[l] is in countT and window[s[l]] < countT[s[l]], decrement have.
• Increment l.

6. Return the substring defined by the best l, r found.

def min_window(s: str, t: str) -> str:
    if t == "": return ""

    countT, window = {}, {}
    for c in t:
        countT[c] = 1 + countT.get(c, 0)

    have, need = 0, len(countT)
    res, resLen = [-1, -1], float("inf")
    l = 0

    for r in range(len(s)):
        c = s[r]
        window[c] = 1 + window.get(c, 0)

        if c in countT and window[c] == countT[c]:
            have += 1

        while have == need:
            # Update our result
            if (r - l + 1) < resLen:
                res = [l, r]
                resLen = (r - l + 1)

            # Pop from the left of our window
            window[s[l]] -= 1
            if s[l] in countT and window[s[l]] < countT[s[l]]:
                have -= 1
            l += 1

    l, r = res
    return s[l : r + 1] if resLen != float("inf") else ""

Time & Space Complexity

• Time complexity: O(n + m)

• Reason: We iterate through s once with r and at most once with l. Constructing the initial map takes O(m).

• Space complexity: O(1) or O(m + n)

• Reason: The dictionaries store at most the size of the character set (e.g., 52 for English letters).