LeetCode 76: Minimum Window Substring Solution in Python Explained

Problem Statement

LeetCode 76, Minimum Window Substring, is a hard-level problem where you’re given two strings s and t. Your task is to find the minimum window substring of s that contains all characters in t (including duplicates) and return it. If no such substring exists, return an empty string. The solution should be efficient, ideally O(n) time complexity, where (n) is the length of s.

Constraints

1 <= s.length, t.length <= 10^5: String lengths are between 1 and 100,000.
s and t consist of English letters (uppercase and lowercase).

Example

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the shortest substring of s containing A, B, and C.

Input: s = "a", t = "a"
Output: "a"
Explanation: Single character matches t.

Input: s = "a", t = "aa"
Output: ""
Explanation: No substring contains two 'a's.

Understanding the Problem

How do you solve LeetCode 76: Minimum Window Substring in Python? For s = "ADOBECODEBANC" and t = "ABC", find the smallest substring of s that includes all characters in t—here, it’s "BANC". We need to track character frequencies and use a sliding window to minimize the substring length. We’ll explore two approaches: a Sliding Window with Hash Map Solution (optimal and primary) and an Alternative with Array Counting (similar but using arrays). The hash map method runs in O(n) time with O(k) space, where (k) is the size of the character set.

Solution 1: Sliding Window with Hash Map Approach (Primary)

Explanation

Use a sliding window with two pointers (left and right) and a hash map to track the count of characters in t. Expand the window by moving right until all characters in t are included (valid window), then shrink it by moving left to minimize the length while maintaining validity. Update the minimum window whenever a smaller valid window is found.

Here’s a flow for s = "ADOBECODEBANC", t = "ABC":

t_count = {'A':1, 'B':1, 'C':1}, required = 3
right=0: "A", have=1
right=5: "ADOBEC", have=3, valid
left=0->3: "BEC", have=2, invalid
right=11: "BECODEBANC", have=3, valid
left=3->9: "BANC", have=3, min_len=4
Result: "BANC"

Initialize Hash Maps.

Count characters in t, track window characters.

Slide Window.

Expand right until valid, shrink left to minimize.

Track Minimum.

Update smallest valid window.

Return Result.

Step-by-Step Example

Example 1: s = "ADOBECODEBANC", t = "ABC"

We need "BANC".

Goal: Find minimum window containing A, B, C.
Result for Reference: "BANC".
Start: s = "ADOBECODEBANC", t = "ABC", t_count = {'A':1, 'B':1, 'C':1}, window = {}, have = 0, need = 3, left = 0, right = 0, min_len = inf, min_window = "".
Step 1: right = 0, 'A'.

window = {'A':1}, have = 1, need = 3.

Step 2: right = 1, 'D'.

window = {'A':1, 'D':1}, have = 1.

Step 3: right = 2, 'O'.

window = {'A':1, 'D':1, 'O':1}, have = 1.

Step 4: right = 3, 'B'.

window = {'A':1, 'D':1, 'O':1, 'B':1}, have = 2.

Step 5: right = 4, 'E'.

window = {'A':1, 'D':1, 'O':1, 'B':1, 'E':1}, have = 2.

Step 6: right = 5, 'C'.

window = {'A':1, 'D':1, 'O':1, 'B':1, 'E':1, 'C':1}, have = 3, valid.
Shrink: left = 0, 'A', window = {'A':0, 'D':1, 'O':1, 'B':1, 'E':1, 'C':1}, have = 2.
left = 1, 'D', window = {'A':0, 'D':0, 'O':1, 'B':1, 'E':1, 'C':1}, have = 2.
left = 2, 'O', window = {'A':0, 'D':0, 'O':0, 'B':1, 'E':1, 'C':1}, have = 2.
left = 3, 'B', window = {'A':0, 'D':0, 'O':0, 'B':0, 'E':1, 'C':1}, have = 1, stop.

Step 7: right = 6, 'O'.

window = {'A':0, 'D':0, 'O':1, 'B':0, 'E':1, 'C':1}, have = 1.

Step 8: Continue to right = 9, 'B'.

window = {'A':0, 'D':0, 'O':1, 'B':1, 'E':1, 'C':1, 'D':1}, have = 2.

Step 9: right = 11, 'C'.

window = {'A':1, 'D':0, 'O':1, 'B':1, 'E':1, 'C':1, 'N':1}, have = 3, valid.
min_len = 10, min_window = "ECODEBANC".
Shrink: left = 3 to 9, "BANC", have = 3, min_len = 4, min_window = "BANC".

Finish: Return "BANC".

How the Code Works (Sliding Window with Hash Map)

Here’s the Python code with line-by-line explanation:

from collections import Counter

def minWindow(s: str, t: str) -> str:
    # Line 1: Handle edge case
    if not s or not t:
        return ""

    # Line 2: Initialize t character counts
    t_count = Counter(t)
    need = len(t_count)

    # Line 3: Initialize window variables
    window = {}
    have = 0
    left = right = 0
    min_len = float('inf')
    min_window = ""

    # Line 4: Slide window
    while right < len(s):
        # Line 5: Expand window
        char = s[right]
        window[char] = window.get(char, 0) + 1
        if char in t_count and window[char] == t_count[char]:
            have += 1
        right += 1

        # Line 6: Shrink window when valid
        while have == need:
            curr_len = right - left
            if curr_len < min_len:
                min_len = curr_len
                min_window = s[left:right]

            char = s[left]
            window[char] -= 1
            if char in t_count and window[char] < t_count[char]:
                have -= 1
            left += 1

    # Line 7: Return minimum window
    return min_window

Alternative: Array Counting Approach

Explanation

Use arrays instead of hash maps for character counting (assuming ASCII characters), tracking required and window counts. The logic mirrors the hash map approach but avoids dictionary overhead, potentially faster for small character sets.

Initialize Arrays.

128-size arrays for ASCII.

Slide Window.

Same expansion and shrinking logic.

Return Result.

Step-by-Step Example (Alternative)

For s = "ADOBECODEBANC", t = "ABC":

Start: t_count[65]=1 (A), t_count[66]=1 (B), t_count[67]=1 (C), need = 3.
Step 1: Expand to "ADOBEC", have = 3, shrink to invalid, continue.
Step 2: Expand to "BECODEBANC", have = 3, shrink to "BANC", min_len = 4.
Finish: Return "BANC".

How the Code Works (Array Counting)

def minWindowArray(s: str, t: str) -> str:
    # Line 1: Handle edge case
    if not s or not t:
        return ""

    # Line 2: Initialize arrays
    t_count = [0] * 128
    window = [0] * 128
    for char in t:
        t_count[ord(char)] += 1

    # Line 3: Count required distinct chars
    need = sum(1 for count in t_count if count > 0)
    have = 0

    # Line 4: Slide window
    left = right = 0
    min_len = float('inf')
    min_window = ""
    while right < len(s):
        char = s[right]
        window[ord(char)] += 1
        if t_count[ord(char)] > 0 and window[ord(char)] == t_count[ord(char)]:
            have += 1
        right += 1

        while have == need:
            curr_len = right - left
            if curr_len < min_len:
                min_len = curr_len
                min_window = s[left:right]
            char = s[left]
            window[ord(char)] -= 1
            if t_count[ord(char)] > 0 and window[ord(char)] < t_count[ord(char)]:
                have -= 1
            left += 1

    # Line 5: Return minimum window
    return min_window

Complexity

Sliding Window with Hash Map:

Time: O(n) – Single pass with two pointers.
Space: O(k) – Hash map size, where \(k\) is charset size.

Array Counting:

Time: O(n) – Single pass.
Space: O(1) – Fixed 128-size arrays.

Efficiency Notes

Sliding Window with Hash Map is O(n) time and O(k) space, optimal for LeetCode 76 with a general charset. Array Counting is O(n) time and O(1) space (fixed array size), slightly more efficient in space for ASCII but less flexible. Both meet the efficiency goal.

Key Insights

Tips to master LeetCode 76:

Sliding Window: Expand until valid, shrink to minimize.
Char Counting: Track required vs. current counts.
Two Pointers: Optimize with left and right movements.

Additional Example

For s = "aa", t = "aa":

Goal: "aa".
Hash Map: Window "aa", have=1, need=1, return "aa".
Result: "aa".

Edge Cases

Empty Strings: s="", t="a" – Return "".
Single Char: s="a", t="a" – Return "a".
No Match: s="abc", t="def" – Return "".

Final Thoughts

The Sliding Window with Hash Map solution is a powerful pick for LeetCode 76 in Python—flexible, efficient, and clear, with Array Counting as a space-saving twist. For a related challenge, try LeetCode 75: Sort Colors to switch to sorting! Ready to find windows? Solve LeetCode 76 on LeetCode now and test it with "ADOBECODEBANC" and "ABC" to master substring searching. Dive in and slide to success!