Introduction to Sliding Window
Learn how to turn O(N²) brute-force solutions into O(N) by maintaining a dynamic window of elements.
Examples
"abc" is the longest stretch with no repeated character, so the answer is 3.
Every character is "b", so no stretch longer than 1 avoids a repeat.
What is the Sliding Window Technique?
The Sliding Window is a technique used to perform operations on a specific subset of data (a window) that moves across a larger dataset (usually an array or string).
Imagine looking at a long train through a small rectangular frame. As the train moves, you see different parts of it, but your frame either keeps its size or expands and contracts. This allows us to process data sequentially without having to re-calculate everything from scratch for every subarray.
The Motivation: Longest Substring
Let's learn this with a classic problem: Longest Substring Without Repeating Characters.
"Given a string
s, find the length of the longest substring that contains no duplicate characters."
Example: s = "abcabcbb"
abc(Length 3) - Validabca(Length 4) - Invalid ('a' repeats)bcabc...
How do we find the maximum length efficiently?
Attempt 1: Brute Force (Why it fails)
The naive approach is to check every possible substring.
- Start at index 0 ('a'). Check substrings: 'a', 'ab', 'abc', 'abca'...
- Start at index 1 ('b'). Check substrings: 'b', 'bc', 'bca'...
The Problem:
- Time Complexity: O(N^3) or O(N^2) depending on implementation.
- Redundant Work: When checking 'abc' then 'abcd', we re-scan 'abc' unnecessarily. We should just ask: "Can we add 'd'?"
When should I use Sliding Window?
Pattern Recognition Triggers:
Use this technique when:
- Contiguous: The problem asks for a contiguous subarray or substring.
- Running Calculation: You need to calculate something (sum, average, count, max length) over a subset.
- Constraints: The input size is large (e.g., 10^5), requiring an O(N) solution.
- Keywords: "Longest", "Shortest", "Maximum Sum", "Minimum Length".
The Intuition: Expand and Contract
Instead of starting from scratch, let's treat the substring as a growing and shrinking window.
The Algorithm:
- Expand (Right): Extend the window by adding elements one by one.
- Validate: Check if the window is currently valid (e.g., no duplicates).
- Contract (Left): If invalid, shrink the window from the left until it becomes valid again.
- Update: Keep track of the best solution found during valid states.
Interactive Walkthrough
"abcabcbb" · 8 CHARACTERS
EMPTY WINDOW
0
1
2
3
4
5
6
7
Checks
0
Length
—
Best
0
seen (last index)
Nothing seen yet
The window starts empty at index 0, with no characters seen
Next
Read 'a' at 0
String
Legend & Complexity
Solid frame: the current window or substring, with no repeat
Dashed frame: it repeats a character
The earlier copy of the repeated character
Sliding window: characters left behind by L
The longest substring found
Every substring
O(n²)
Sliding window
O(n)
Space
O(min(n, charset))
In Sliding window mode, left and right define the window: each character is read once, and left jumps straight past a repeat. Switch to Check every substring to watch the brute force grow a substring from every start instead. Checks counts the characters each method examines.
Dry Run Table
| Step | Window | Seen Map | Action |
|---|---|---|---|
| 1 | [a] |
{a:0} |
Expand R. Valid. Max=1. |
| 2 | [a, b] |
{a:0, b:1} |
Expand R. Valid. Max=2. |
| 3 | [a, b, c] |
{a:0, b:1, c:2} |
Expand R. Valid. Max=3. |
| 4 | [a, b, c, a] |
{a:3...} |
Duplicate 'a'! Invalid. |
| 5 | [b, c, a] |
{a:3, b:1, c:2} |
Contract L past old 'a' (index 0). New Start=1. Valid. |
The Solution Template
Most sliding window problems follow this exact pattern. Memorize it.
def sliding_window(data):
left = 0
current_window = ... # Map, Set, or Sum var
best_answer = ...
for right in range(len(data)):
# 1. EXPAND: Add data[right] to window
add_to_window(data[right])
# 2. CONTRACT: While window is invalid
while condition_broken():
remove_from_window(data[left])
left += 1
# 3. PROCESS: Update answer if valid
best_answer = max(best_answer, right - left + 1)
return best_answer
Introduction to Sliding Window Code
1var lengthOfLongestSubstring = function(s) {2 let seen = new Map();3 let left = 0;4 let maxLen = 0;56 for (let right = 0; right < s.length; right++) {7 let char = s[right];8 if (seen.has(char) && seen.get(char) >= left) {9 left = seen.get(char) + 1;10 }11 seen.set(char, right);12 maxLen = Math.max(maxLen, right - left + 1);13 }14 return maxLen;15};
Edge Cases & Common Mistakes
Edge Case Checklist:
- Empty String/Array: Always handle input size 0 or 1.
- K > N: If the problem asks for a window of size
K, handle cases whereN < K. - No Solution: Determine what to return if no valid window exists (e.g. 0, infinity, or empty string).
Common Mistakes:
- Off-by-one: Be careful with window size calculation (
right - left + 1vsright - left). - Shrinking Loop: Using
ifinstead ofwhileto shrink the window. You must keep shrinking until the window becomes valid again. - Update Order: Updating the result variable (max/min) at the wrong time (e.g., before checking validity).
Summary
Recap:
- The Trick: Avoid re-calculating overlapping sub-problems.
- Movement: Expand
rightto find potential matches. Contractleftto satisfy constraints. - Efficiency: Transforms nested loops O(N²) into a linear O(N) single pass.