Sliding window is one of those techniques that once you get it, you’ll start spotting it everywhere. It’s a go-to tool for solving problems involving subarrays, substrings, or continuous sequences and can turn an O(n²) brute-force problem into a sleek O(n) solution. Let’s dive in!
What is Sliding Window?
A sliding window helps you iterate through a series of elements in segments. It takes in each element one by one to check a condition, and removes elements when the condition is no longer met.
How Does It Work?
- The window moves from left to right.
- Each element is taken into the window to check if it satisfies a specific condition.
- We use two pointers, usually named l (left) and r (right).
Step-by-Step Explanation:
1. Initialize the two pointers:
Start with both l and r at the beginning of the array or string.
2. Expand the window:
While the condition is not yet satisfied, move the r pointer forward to increase the window size.
3. Check the condition:
As you include new elements, check if the current window meets the required condition (e.g., sum ≤ target, valid substring, etc.).
4. Shrink the window if needed:
If the condition fails, move the l pointer forward to reduce the window size and try to regain a valid window.
Example:
Imagine a sliding window: l is the left blade, and r is the right blade.
If we keep one side of the window constant (say, l), and move the other side (r), the window expands; this is how the sliding window works:
When the condition is not satisfied, we change the position of l to the next element. This marks the starting of the new window, and we check through elements using both pointers to find a new valid window.
- Moving l helps reduce the window size.
- Moving r helps determine the window’s right boundary.
Why Do We Use Sliding Window?
Sliding windows are usually used to return a group of elements when our required output is a maximum value, sum, or any condition based on grouping.
The sliding window method helps us to:
Find the output by performing operations on a group of elements stored in a window.
Segment the list into all possible groups and check for the required condition.
💡 Key Benefits:
- Makes the process easier by reducing time complexity.
- We don’t need to check the already-checked groups again.
- Efficient in problems where we need to slide over input and check conditions dynamically.
LeetCode Example:
Let’s see how sliding window logic can solve one of the most asked interview question.
Longest Repeating Character Replacement: (Leetcode no.3)
Given a string s and an integer k, find the length of the longest substring where you can replace at most k characters to make all characters the same.
Example
Input: s = „AABABB“, k = 2
We want the longest substring where we can replace at most 2 characters to make all characters the same.
Step-by-Step Logic
We apply the rule:
window size - max frequency ≤ k
Where:
- window size = r – l + 1
- max frequency = most repeated character in current window
If true:
We can replace the remaining characters → Expand window
If false:
Too many replacements needed → Shrink window from the left
Walkthrough:
Best window = „AABAB“
Max freq = 3 (A)
Replacements needed = 5 – 3 = 2
✅ 2 ≤ k → valid window
Result = 5
This is a classic sliding window problem:
📌 Expand → Check Condition → Shrink if needed → Track max