The sliding window technique is a powerful algorithmic pattern used to solve problems involving subarrays or substrings. Instead of checking every possible window with nested loops (which would be O(n²) or worse), sliding window maintains a dynamic window that expands and contracts based on certain conditions, achieving linear or near-linear time complexity.
The core idea is to use two pointers to represent the boundaries of a 'window' in your data structure. You typically start with both pointers at the beginning, then move the right pointer to expand the window until some condition is met. Once the condition is satisfied, you try to shrink the window from the left while maintaining that condition, keeping track of the optimal solution found so far.
There are two main variants: fixed-size windows where the window size remains constant as it slides, and variable-size windows where the window grows and shrinks based on the problem's constraints. Variable-size windows are particularly useful for optimization problems where you're looking for the minimum or maximum window that satisfies certain criteria.
The technique is especially effective for problems involving contiguous elements, such as finding subarrays with specific sums, substrings with certain character patterns, or sequences that meet particular conditions. It transforms what would otherwise be expensive nested iterations into a single pass through the data.
1def longest_substring_with_k_distinct(s, k):
2 """Find longest substring with at most k distinct characters"""
3 if k == 0:
4 return 0
5
6 left = 0
7 char_count = {}
8 max_length = 0
9
10 for right in range(len(s)):
11 # Expand window by adding right character
12 char = s[right]
13 char_count[char] = char_count.get(char, 0) + 1
14
15 # Shrink window if we have too many distinct characters
16 while len(char_count) > k:
17 left_char = s[left]
18 char_count[left_char] -= 1
19 if char_count[left_char] == 0:
20 del char_count[left_char]
21 left += 1
22
23 # Update maximum length found
24 max_length = max(max_length, right - left + 1)
25
26 return max_length