Sliding Window for Substrings
Implement the variable-size sliding window to find the longest substring without repeating characters and the minimum window containing all target characters.
The Sliding Window Concept
A sliding window maintains a subarray (or substring) between a left and right pointer. Instead of recomputing properties of every possible subarray from scratch in O(n²), the window expands right by adding one element and contracts left by removing one element, maintaining a running state in O(1) per step. The result is an O(n) algorithm. The window is called 'sliding' because it moves forward through the array without going backward.
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])Fixed vs Variable Window Size
There are two flavours of sliding window. In a fixed-size window, both pointers advance at the same pace and the window always has exactly k elements. In a variable-size window, the right pointer expands greedily and the left pointer contracts only when the window violates a constraint. Variable-size windows solve problems like 'longest substring without repeating characters' where the optimal window size is unknown ahead of time.
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2All lessons in this course
- Python String API for Interviews
- Sliding Window for Substrings
- Anagrams and Character Frequency Maps
- String Encoding, Reversal, and Palindromes