Here is the problem of Minimum Window Substring.

1. Understand the problem

Goal: Given strings s (source) and t (target), find the smallest substring in s that contains all characters of t with at least the same counts. Return that substring; if none exists, return “”.

Important details to keep in mind (common interview gotchas):

• Characters are case-sensitive (A ≠ a).

• t may contain duplicates → counts matter.

• If t is empty, what to return? (conventionally “” or maybe s — we should clarify).

• If s is empty or shorter than t, return “”.

2. Clarifying questions

1. What are allowed characters? ASCII? Unicode?

2. Are s and t non-empty? What to return if t is empty?

=> If t is empty, return “”, due to “” is the shortest string that match with t.

1. Should solution be optimized for time? Any expected complexity?

2. Should we return the first minimum window if multiple windows have same length?

=> Return the leftmost one.

1. Are characters only lowercase or uppercase mixed ? For example: s= aBcEd, t = aE

2. Do special character allowed ?

3. Work through examples

1. s = “ADOBECODEBANC”, t = “ABC” → expected “BANC” (smallest window with A,B,C).

2. s = “a”, t = “a” → “a”.

3. s = “a”, t = “aa” → “” (not enough as).

4. s = “ab”, t = “A” → “” (case-sensitive).

5. s = “aa”, t = “aa” → “aa”.

6. s = “”, t = “” → “”.

7. s = “bba”, t = “ab” → “ba” (or “ab” if present; here “ba”).

8. s = “ADOBECODEBANC”, t = “ABBC” → “” (not enough Bs).

9. s = “this is a test string”, t = “tist” → “t stri”? (Check multiplicity: t has t:2,i:1,s:1 — smallest window that contains two t’s etc.)

10. Large duplication case: s long with many repeats, t has many duplicates — we need multiplicities honored.

4. Brainstorm 2–3 solutions & complexity

4.1. Naive solution (brute force):

• Check every substring s[i:j] and test if it covers t using a frequency map.

• Time: O(n^2 * k) where k is cost to check coverage (or O(n^2 * alphabet)), too slow for large n => Compare O(26) with O(26) => K = 26.

• Space: O(alphabet).

4.2. Optimized sliding window (two pointers + counts) — preferred:

• Maintain a window [l, r) and expand r until the window contains all chars of t. Then move l to shrink while still valid. Track minimal window.

• Use need map for counts required and window map for counts in current window (or keep a formed counter to know when window satisfies all required counts).

• Time: O(n + m) (each character visited at most twice).

• Space: O(k) for maps.

Notes:

1. Sliding Window: traverse left and right, so time complexity is O(N).

Time complexity: O(2N)

1. Optimize compare 2 dynamic maps in sliding window with O(1).

• Step 1: Idea using 2 variables to compare maps, can O(1).

need = {'A': 1, 'B': 1, 'C': 1}
window = {}
formed = 0
required = len(need)  # = 3

• Step 2: Increase the match when reach.

ch = s[r]
window[ch] += 1
if ch in need and window[ch] == need[ch]:
    formed += 1

• Step 3: Decrease the match when shrink and it not suitable.

left_char = s[l]
window[left_char] -= 1
if left_char in need and window[left_char] < need[left_char]:
    formed -= 1

5. Implement solutions

5.1. Brute Force - O(N^2 * M)

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "":
            return ""

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

        res, resLen = [-1, -1], float("infinity")
        for i in range(len(s)):
            countS = {}
            for j in range(i, len(s)):
                countS[s[j]] = 1 + countS.get(s[j], 0)

                flag = True
                for c in countT:
                    if countT[c] > countS.get(c, 0):
                        flag = False
                        break

                if flag and (j - i + 1) < resLen:
                    resLen = j - i + 1
                    res = [i, j]

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

• Time complexity: O(N^2 * M).

• Space complexity: O(M).

5.2. Sliding Window using alphabet map with 26 characters - O(52 * 2N)

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""

        # Map 'A'-'Z' → 0–25, 'a'-'z' → 26–51
        def idx(c):
            o = ord(c)
            if 'A' <= c <= 'Z':
                return o - ord('A')
            elif 'a' <= c <= 'z':
                return 26 + (o - ord('a'))
            else:
                # optionally handle other chars (digits, symbols)
                return None

        # Initialize frequency maps
        need = [0] * 52
        window = [0] * 52

        for c in t:
            need[idx(c)] += 1

        # Helper: check if window covers need
        def contains_all():
            for i in range(52):
                if window[i] < need[i]:
                    return False
            return True

        l = 0
        min_len = float('inf')
        min_l = 0

        for r, ch in enumerate(s):
            if idx(ch) is None:
                continue  # skip non-letter chars

            window[idx(ch)] += 1

            # Try to shrink when window valid
            while contains_all() and l <= r:
                curr_len = r - l + 1
                if curr_len < min_len:
                    min_len = curr_len
                    min_l = l

                # Shrink from left
                window[idx(s[l])] -= 1
                l += 1

        return "" if min_len == float('inf') else s[min_l:min_l + min_len]

• Idea: Using a hashmap 26 alphabet to compare current window and target O(26), slide in sliding window is O(2N) => O(26 * 2N) => In this case, we are using O(52) for storing A-Z, a-z.

• Time complexity: O(52 * 2N).

• Space complexity: O(52).

5.3. Sliding Window using variables - O(N + M)

class Solution:
    def minWindow(self, 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("infinity")
        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:
                if (r - l + 1) < resLen:
                    res = [l, r]
                    resLen = r - l + 1

                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("infinity") else ""

• Idea: using a variables to count, matched = len(t).

• Time complexity: O(N + M).

• Space: O(M).

6. Dry run testcases

s = "ADOBECODEBANC", t = "ABC"

Step 1:

Step 2: