How to Solve: Minimum Window Substring

How to Solve: Minimum Window Substring

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can handle sliding windows, hash maps, and edge-case optimization at a senior-engineer level."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Minimum Window Substring, ensure you understand: 1. Hash Maps (Dictionaries) – For tracking character frequencies in O(1) time. 2. Sliding Window Technique – Expanding and contracting a window to find valid substrings efficiently. 3. Two-Pointer Technique – Using left and right pointers to traverse the string in O(n) time.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeat this checklist for every Minimum Window Substring problem.)

1. Edge Cases First
2. If s is empty, t is empty, or len(t) > len(s), return "".

3. If t has duplicate characters, account for their counts.

4. Initialize Frequency Map for t

5. Create a hash map target_counts to store character frequencies in t.

6. required = len(target_counts) (number of unique characters to match).

7. Sliding Window Setup

8. left = 0, right = 0 (two pointers).
9. window_counts = {} (track characters in the current window).
10. formed = 0 (number of unique characters in t that are satisfied in the window).

11. min_len = ∞, result = "" (track the smallest valid window).

12. Expand the Window (Move right)

13. Add s[right] to window_counts.

14. If s[right] is in target_counts and window_counts[s[right]] == target_counts[s[right]], increment formed.

15. Contract the Window (Move left)

16. While formed == required (window is valid):

    • Update min_len and result if the current window is smaller.
    • Remove s[left] from window_counts.
    • If s[left] was in target_counts and its count drops below target_counts[s[left]], decrement formed.
    • Increment left.

17. Terminate & Return

18. If min_len is still ∞, return "".
19. Otherwise, return result.

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 76)

Problem: Given strings s = "ADOBECODEBANC" and t = "ABC", return the minimum window in s that contains all characters of t.

Step-by-Step Walkthrough: 1. Edge Cases:
- s and t are non-empty, len(t) <= len(s) → proceed.

1. Frequency Map for t:
   python
target_counts = {'A': 1, 'B': 1, 'C': 1}
required = 3

2. Sliding Window Setup:
   python
left = right = 0
window_counts = {}
formed = 0
min_len = float('inf')
result = ""

3. Expand right:

4. right = 0 → 'A' → window_counts = {'A':1} → formed = 1 (since 'A' is satisfied).
5. right = 1 → 'D' → not in t → skip.
6. right = 2 → 'O' → skip.
7. right = 3 → 'B' → window_counts = {'A':1, 'B':1} → formed = 2.
8. right = 4 → 'E' → skip.

9. right = 5 → 'C' → window_counts = {'A':1, 'B':1, 'C':1} → formed = 3 (valid window).

10. Contract left:

11. Current window: "ADOBEC" (indices 0-5).
12. Update min_len = 6, result = "ADOBEC".
13. left = 0 → 'A' → window_counts['A'] = 0 → formed = 2 (invalid).
14. left = 1 → 'D' → skip.
15. left = 2 → 'O' → skip.
16. left = 3 → 'B' → window_counts['B'] = 0 → formed = 1 (invalid).
17. left = 4 → 'E' → skip.

18. left = 5 → 'C' → window_counts['C'] = 0 → formed = 0 (invalid).

19. Continue Expanding:

20. right = 6 → 'O' → skip.
21. right = 7 → 'D' → skip.
22. right = 8 → 'E' → skip.
23. right = 9 → 'B' → window_counts = {'B':1} → formed = 1.
24. right = 10 → 'A' → window_counts = {'B':1, 'A':1} → formed = 2.
25. right = 11 → 'N' → skip.

26. right = 12 → 'C' → window_counts = {'B':1, 'A':1, 'C':1} → formed = 3 (valid window).

27. Contract left Again:

28. Current window: "CODEBA" (indices 6-12).
29. min_len = 6 (no improvement).
30. left = 6 → 'O' → skip.
31. left = 7 → 'D' → skip.
32. left = 8 → 'E' → skip.
33. left = 9 → 'B' → window_counts['B'] = 0 → formed = 2 (invalid).
34. left = 10 → 'A' → window_counts['A'] = 0 → formed = 1 (invalid).
35. left = 11 → 'N' → skip.

36. left = 12 → 'C' → window_counts['C'] = 0 → formed = 0 (invalid).

37. Final Window:

38. right = 12 (end of string).
39. Best window: "BANC" (indices 9-12, length 4).

Final Code:

from collections import defaultdict

def minWindow(s: str, t: str) -> str:

    if not s or not t or len(t) > len(s):

        return ""


    target_counts = defaultdict(int)

    for char in t:

        target_counts[char] += 1

    required = len(target_counts)


    left = right = 0

    window_counts = defaultdict(int)

    formed = 0

    min_len = float('inf')

    result = ""


    while right < len(s):

        char = s[right]

        window_counts[char] += 1


        if char in target_counts and window_counts[char] == target_counts[char]:

            formed += 1


        while left <= right and formed == required:

            current_window_len = right - left + 1

            if current_window_len < min_len:

                min_len = current_window_len

                result = s[left:right+1]


            left_char = s[left]

            window_counts[left_char] -= 1

            if left_char in target_counts and window_counts[left_char] < target_counts[left_char]:

                formed -= 1

            left += 1


        right += 1


    return result

Time Complexity: O(|s| + |t|) (each character is processed at most twice). Space Complexity: O(|s| + |t|) (for the hash maps).

Why This Works: - The sliding window ensures we only traverse s once while dynamically adjusting the window to find the smallest valid substring. - The formed counter guarantees we only consider windows that contain all characters of t.

Example 2 – Medium (Duplicates in t)

Problem: s = "AAABBBCA", t = "ABCA" → Return "ABBBCA" (smallest window with at least 1 'A', 1 'B', 1 'C', and 1 'A').

Key Twist: - t has duplicate 'A' → target_counts = {'A':2, 'B':1, 'C':1}.

Solution: - The same framework applies, but formed only increments when window_counts[char] == target_counts[char] (not just >=).

Final Code: (Same as above, but target_counts now has 'A':2.)

Why This Works: - The formed counter ensures we don’t count a character as "satisfied" until its count in the window matches its count in t.

Example 3 – Hard (Follow-Up: Minimum Window with All Distinct Characters)

Problem: Given s = "aabdec", find the smallest substring containing all distinct characters of s (i.e., 'a', 'b', 'd', 'e', 'c').

Key Twist: - t is not given; instead, we must find all distinct characters in s first.

Solution: 1. Compute target_counts as the frequency of all distinct characters in s. 2. Apply the same sliding window framework.

Final Code:

from collections import defaultdict

def minWindowAllDistinct(s: str) -> str:

    if not s:

        return ""


    target_counts = defaultdict(int)

    for char in s:

        target_counts[char] += 1

    required = len(target_counts)


    left = right = 0

    window_counts = defaultdict(int)

    formed = 0

    min_len = float('inf')

    result = ""


    while right < len(s):

        char = s[right]

        window_counts[char] += 1


        if window_counts[char] == target_counts[char]:

            formed += 1


        while left <= right and formed == required:

            current_window_len = right - left + 1

            if current_window_len < min_len:

                min_len = current_window_len

                result = s[left:right+1]


            left_char = s[left]

            window_counts[left_char] -= 1

            if window_counts[left_char] < target_counts[left_char]:

                formed -= 1

            left += 1


        right += 1


    return result

Time Complexity: O(|s|) (each character is processed twice). Space Complexity: O(|s|) (for the hash maps).

Why This Works: - The problem reduces to the same sliding window pattern, but we first compute target_counts from s itself.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Minimum Window Substring is all about sliding windows and hash maps. Here’s the playbook:

1. Edge Cases First: If s or t is empty, or t is longer than s, return "".
2. Frequency Map: Build target_counts for t and track required unique characters.
3. Sliding Window: Expand right until the window is valid (formed == required), then contract left to find the smallest window.
4. Update Result: Whenever the window is valid, check if it’s the smallest so far.
5. Terminate Early: If the remaining window can’t be smaller, break early.

Remember: The key is formed vs. required. Only contract left when the window is valid, and only decrement formed when a character’s count drops below its target. Practice this 3 times, and you’ll crush it in the interview. Good luck!

? Final Notes

• Practice Variations:
• LeetCode 76 (Minimum Window Substring)
• LeetCode 3 (Longest Substring Without Repeating Characters) (similar sliding window)
• LeetCode 438 (Find All Anagrams in a String) (fixed-size window)
• Time Yourself: Aim for 15-20 minutes to solve this problem cleanly in an interview.
• Whiteboard First: Always sketch the sliding window and hash maps before coding.

You’ve got this! ?