Smallest Window Containing All Features

Smallest Window Containing All Features

This problem requires finding the minimum length contiguous substring of features that contains all unique characters from required (with their required frequencies). It's a classic Sliding Window + Required Characters Coverage problem.

1. Background Knowledge

Key Concepts:

• Sliding Window Technique: Maintain a window [left, right] that expands/contracts to satisfy conditions
• Character Frequency Tracking: Count occurrences of each required character in current window
• Coverage Condition: Window is valid when every character in required appears ≥ its required count
• Two-Pointer Technique: right expands window, left contracts when condition met to minimize size

Prerequisites:

• Hash maps/dictionaries for O(1) frequency updates
• Understanding of amortized analysis for sliding window

2. Algorithm Approach

Optimal Algorithm: Sliding Window with Counter Tracking

1. Count required frequencies: req_count[char] = frequency in 'required'
2. Track current window frequencies: window_count[char]
3. Maintain 'needed' = number of unique characters still required
4. Expand right pointer, update window_count
5. When needed == 0, record min_length, shrink left pointer
6. Repeat until right reaches end

Time Complexity: $O(n + m)$ where $n = |features|$, $m = |required|$ Space Complexity: $O(|\Sigma|)$ where $\Sigma$ is alphabet size (≤52 for English letters)

Why Optimal? Each character processed at most twice (right expansion + left contraction)

3. Step-by-Step Strategy

def smallest_window(features: str, required: str) -> int:
 if not required or not features:
 return 0

 # Step 1: Count required frequencies
 req_count = {}
 for char in required:
 req_count[char] = req_count.get(char, 0) + 1

 needed = len(req_count) # Unique chars needed
 window_count = {}
 left = 0
 min_len = float('inf')

 # Step 2: Slide window
 for right in range(len(features)):
 char = features[right]