🟥 Minimum Window Substring (#76)

🔗 Problem Link

• LeetCode - Minimum Window Substring
• NeetCode - Minimum Window Substring

📋 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 "".

💡 Examples

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.

🔑 Key Insights & Approach

Core Observation: Use sliding window that expands right until valid, then contracts left to minimize while maintaining validity.

Why Sliding Window + HashMap?

• Track character frequencies needed and current window
• Expand window until all characters satisfied
• Contract window to find minimum
• O(n) time complexity

Approaches:

1. Brute force all substrings: O(n²)
2. Sliding window with frequency maps: O(n + m) - optimal

Pattern: "Sliding Window - Minimum Window" pattern for substring with conditions.

🐍 Solution: Python

Approach: Sliding Window with Two HashMaps

Time Complexity: O(n + m) | Space Complexity: O(m)

from collections import Counter

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

        # Count characters needed
        target_count = Counter(t)
        required = len(target_count)

        # Window state
        window_count = {}
        have = 0  # number of unique chars in window with correct frequency

        # Result
        result = [-1, -1]  # [left, right]
        min_length = float('inf')

        left = 0

        for right in range(len(s)):
            char = s[right]
            window_count[char] = window_count.get(char, 0) + 1

            # Check if this character's frequency matches target
            if char in target_count and window_count[char] == target_count[char]:
                have += 1

            # Contract window while valid
            while have == required:
                # Update result
                if (right - left + 1) < min_length:
                    min_length = right - left + 1
                    result = [left, right]

                # Remove from left
                left_char = s[left]
                window_count[left_char] -= 1

                if left_char in target_count and window_count[left_char] < target_count[left_char]:
                    have -= 1

                left += 1

        left, right = result
        return s[left:right+1] if min_length != float('inf') else ""

🔵 Solution: Golang

Approach: Sliding Window

Time Complexity: O(n + m) | Space Complexity: O(m)

func minWindow(s string, t string) string {
    if len(t) == 0 || len(s) == 0 {
        return ""
    }

    // Count target characters
    targetCount := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        targetCount[t[i]]++
    }
    required := len(targetCount)

    // Window state
    windowCount := make(map[byte]int)
    have := 0

    // Result
    minLen := len(s) + 1
    result := []int{-1, -1}
    left := 0

    for right := 0; right < len(s); right++ {
        char := s[right]
        windowCount[char]++

        if count, exists := targetCount[char]; exists && windowCount[char] == count {
            have++
        }

        // Contract window
        for have == required {
            // Update result
            if right-left+1 < minLen {
                minLen = right - left + 1
                result = []int{left, right}
            }

            // Remove from left
            leftChar := s[left]
            windowCount[leftChar]--

            if count, exists := targetCount[leftChar]; exists && windowCount[leftChar] < count {
                have--
            }

            left++
        }
    }

    if result[0] == -1 {
        return ""
    }
    return s[result[0] : result[1]+1]
}

📚 References

• NeetCode - Minimum Window Substring