📘 Sliding Window Technique
🔍 What Is the Sliding Window Technique?
The Sliding Window is a powerful technique used to reduce the time complexity of problems involving contiguous subarrays or substrings.
Instead of using nested loops (\(O(n^2)\)), we “slide” a window of fixed or variable size across the input, adjusting it as we go — reducing most problems to \(O(n)\) time.
When to Use Sliding Window
-
You need to find or optimize subarrays/substrings (e.g., longest, smallest, total).
-
The input is linear (array or string).
-
You’re looking for problems involving:
- Sum / Count / Max / Min of a subarray
- Substring with unique or repeated elements
- Fixed or variable-sized window
🪟 Sliding Window Pattern
Template for fixed-size window
Find Max sum of subarray of size K
def sliding_window_fixed(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
Template for variable-size window
def sliding_window_variable(s):
window = {}
left = 0
result = 0
for right in range(len(s)):
# Expand window by adding s[right]
# window logic here...
while <some_condition>: # shrink
# Shrink window from the left
left += 1
result = max(result, right - left + 1)
return result
Ex : Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
seen = {}
left = 0
max_len = 0
for right, char in enumerate(s):
if char in seen and seen[char] >= left:
left = seen[char] + 1
seen[char] = right
max_len = max(max_len, right - left + 1)
return max_len
📝 Suggested Practice Problems
Easy
Medium
➡ Longest Substring with At Least K Repeating Characters
➡ Longest Subarray with At Most Two Distinct Elements
➡ Longest Repeating Character Replacement
➡ Find the longest subarray with consecutive 1s if you can flip at most k zeros.
Hard