The sliding window technique is a powerful algorithmic pattern used to solve problems involving contiguous subarrays or substrings. Instead of checking every possible substring (which would be O(n³) time complexity), we maintain a "window" that expands and contracts as we traverse the data structure.
The key insight is that we can reuse computations from previous windows. When we move the window, we don't start from scratch – we incrementally update our current state by adding new elements and removing old ones.
For substring problems without repeating characters, we use two pointers: a left pointer marking the window's start and a right pointer marking the end. We also maintain a data structure (like a hash set) to track what's currently in our window.
The algorithm works by:
This approach ensures we visit each character at most twice (once when adding, once when removing), giving us O(n) time complexity. The space complexity is O(min(m,n)) where m is the character set size, since our hash set can't grow larger than the unique characters in the string.
Sliding window is particularly effective for optimization problems on sequences where you need to find optimal contiguous subarrays or substrings.
1def max_sum_subarray(arr, k):
2 """Find maximum sum of any subarray of length k using sliding window."""
3 if len(arr) < k:
4 return 0
5
6 # Calculate sum of first window
7 window_sum = sum(arr[:k])
8 max_sum = window_sum
9
10 # Slide the window: remove leftmost, add rightmost
11 for i in range(k, len(arr)):
12 window_sum = window_sum - arr[i - k] + arr[i]
13 max_sum = max(max_sum, window_sum)
14
15 return max_sum