Pattern 02
Sliding Window
Maintain a summary of one contiguous range while its boundaries move.
Recognize it
Read the constraints before choosing the technique
Subarray or substring
The candidate items must be contiguous, so two boundaries can describe them.
Longest, shortest, maximum, minimum, or count
Many overlapping ranges must be compared.
At most k, no repeats, or within a budget
A compact state can tell whether the current range is valid.
Exactly k consecutive items
The boundaries move together as a fixed-size window.
Cases that look similar but need another approach
The problem says subsequence and gaps are allowed
A window is one uninterrupted range and cannot describe arbitrary gaps.
A target-sum window may contain negative values
With negatives, expanding can reduce the total and shrinking can increase it, so the movement rule is not monotonic.
Every full window must be copied or printed
The output requires the work that a summary would otherwise avoid.
Reasoning
The ideas the code depends on
Subarray is not subsequence
A subarray or substring occupies consecutive positions. A subsequence may skip positions. Sliding window requires the first definition.
Store only what the rule needs
A sum, duplicate count, frequency map, or number of zeros can describe the window without rescanning its middle.
The inner while loop is still linear
The right boundary enters each position once and the left boundary removes each position at most once. Across the whole run there are at most 2n boundary moves.
Procedure
Turn the invariant into a repeatable process
- 01
Move right one position and add that item to the window summary.
- 02
While the rule is broken, remove items from the left and advance left.
- 03
Once valid, compare the current length or score with the best result.
- 04
Repeat until right reaches the end.
Common forms of the pattern
Each element enters once and leaves at most once. The auxiliary state tracks only the active window or its categories.
Implementation
Worked form
Longest substring without repeating characters
Return the length of the longest substring containing no repeated character.
Longest substring without repeating characters
int longestUnique(String text) {
Map<Character, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < text.length(); right++) {
char added = text.charAt(right);
count.put(added, count.getOrDefault(added, 0) + 1);
while (count.get(added) > 1) {
char removed = text.charAt(left++);
count.put(removed, count.get(removed) - 1);
}
best = Math.max(best, right - left + 1);
}
return best;
}def longest_unique(text):
count = {}
left = best = 0
for right, added in enumerate(text):
count[added] = count.get(added, 0) + 1
while count[added] > 1:
removed = text[left]
count[removed] -= 1
left += 1
best = max(best, right - left + 1)
return bestint longestUnique(const string& text) {
unordered_map<char, int> count;
int left = 0, best = 0;
for (int right = 0; right < text.size(); right++) {
char added = text[right];
count[added]++;
while (count[added] > 1) {
count[text[left]]--;
left++;
}
best = max(best, right - left + 1);
}
return best;
}Common implementation mistakes
- Treating subsequence as if it meant substring
- Recomputing the window sum or counts from scratch
- Updating the answer before the window becomes valid
- Assuming the target-sum form works with negative values
Problem family
What stays the same—and what changes
These are not five unrelated solutions. Each problem preserves the movement rule and changes one part of the state or answer.
Maximum Sum of Size K
EasyKeep the width fixed; update one incoming and one outgoing value.
Max Consecutive Ones III
MediumThe summary is the number of zeroes; k is the repair budget.
Longest Repeating Character Replacement
MediumTrack frequency and test window length minus the largest frequency.
Minimum Window Substring
HardRecord while valid, then shrink to find the smallest valid range.
Check yourself