Sliding Window | Hard | Time: O(m + n) | Space: O(m + n)
Use two hash maps to track character frequencies. Expand window with right pointer. When window is valid (contains all chars from t), try to shrink from left. Track the minimum valid window found.
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t or len(s) < len(t):
return ""
# Build frequency map for target string t
count_t = {}
for char in t:
count_t[char] = count_t.get(char, 0) + 1
# Track characters in current window
window = {}
# Variables for tracking valid window
have = 0 # Number of unique chars in window with desired frequency
need = len(count_t) # Number of unique chars needed from t
# Result: [length, left, right]
result = [-1, -1]
min_length = float('inf')
left = 0
# Expand window with right pointer
for right in range(len(s)):
char = s[right]
window[char] = window.get(char, 0) + 1
# Check if this character's frequency matches requirement
if char in count_t and window[char] == count_t[char]:
have += 1
# Try to shrink window from left while valid
while have == need:
# Update result if current window is smaller
current_length = right - left + 1
if current_length < min_length:
min_length = current_length
result = [left, right]
# Remove character from left of window
left_char = s[left]
window[left_char] -= 1
# Check if removing this char breaks validity
if left_char in count_t and window[left_char] < count_t[left_char]:
have -= 1
left += 1
# Return the minimum window substring
left, right = result
return s[left:right + 1] if min_length != float('inf') else ""
Time: O(m + n) - Each character visited at most twice
Space: O(m + n) - Hash maps for character frequencies