Sliding Window (Variable Size)
Expand and shrink a window's right/left edges based on a validity condition to find an optimal-length substring/subarray.
Core technique
Maintain a contiguous window while both edges move forward. For longest-window problems, shrink when the window becomes invalid. For shortest-window problems, shrink while it is valid and record candidates before removing elements. Each index enters once and leaves at most once, so constant-time updates give a linear scan.
How to recognize it
- The question asks for the longest or shortest contiguous subarray or substring that satisfies a condition.
- The condition can be tracked incrementally with a count map, a running sum, or a distinct counter.
- The condition changes predictably as either edge moves. Removing characters can repair an at-most limit; for a minimum-sum target over non-negative numbers, removing values moves toward invalid instead.
- The statement says at most K distinct, without repeating, minimum window, or sum at least target.
Template
This version finds the longest window with at most k distinct characters, for an integer k >= 0. These templates assume ASCII input so character counting is consistent across languages. Measure after shrinking. For shortest-window problems, record the answer while the window is still valid, then shrink.
Python
def longest_at_most_k_distinct(s, k):
counts = {}
left = best = 0
for right, ch in enumerate(s):
counts[ch] = counts.get(ch, 0) + 1
while len(counts) > k:
counts[s[left]] -= 1
if counts[s[left]] == 0:
del counts[s[left]]
left += 1
best = max(best, right - left + 1)
return bestJava
int longestAtMostKDistinct(String s, int k) {
Map<Character, Integer> counts = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
counts.merge(s.charAt(right), 1, Integer::sum);
while (counts.size() > k) {
char drop = s.charAt(left);
if (counts.merge(drop, -1, Integer::sum) == 0) counts.remove(drop);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}JavaScript
function longestAtMostKDistinct(s, k) {
const counts = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);
while (counts.size > k) {
const drop = s[left];
counts.set(drop, counts.get(drop) - 1);
if (counts.get(drop) === 0) counts.delete(drop);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}Worked example: Longest Substring Without Repeating Characters
- Run it on abcabcbb. The window is valid when no character repeats. The template swaps the distinct-count check for a duplicate check, and the shape is identical.
- The right edge reads a, b, c. The window grows to abc, length 3.
- The right edge reads a again. Shrink from the left past the first a, which leaves bca, still length 3.
- The right edge reads b, then c. Each time the older copy leaves first, giving cab and then abc.
- The right edge reads the b at index 6. Shrinking past the older b leaves cb. The final b shrinks the window to b.
- The best length seen is 3, which is the answer.
Complexity: For the no-repeating example: O(n) time and O(min(n, alphabet size)) extra space. For the at-most-k template: O(n) time and O(min(n, k + 1)) extra space, including the temporary character that triggers shrinking.
Try Longest Substring Without Repeating Characters on LeetCodeCommon mistakes
- Recording the best length before the shrink loop finishes. That counts a window that is not valid yet.
- Forgetting to delete a key when its count reaches zero, so the distinct count never goes down.
- Using the usual sum-window rules with negative numbers. Removing a value can increase the sum. Exact-sum counting can use prefix sums with a hash map; shortest-subarray-at-least-target problems may need prefix sums with a monotonic deque.
- Getting the length wrong by one. A window from left to right inclusive holds right - left + 1 elements.
- Confusing counting with longest-window problems. To count subarrays with exactly K distinct values, subtract the at-most-(K - 1) count from the at-most-K count. That subtraction does not compute the longest length.
When this pattern does not fit
- The chosen elements do not have to be contiguous. That is usually dynamic programming or greedy.
- The condition is not monotonic, for example a sum over values that can be negative.
- The window size is fixed at K. The fixed-size window is simpler: add one element, drop one element, and no shrink loop is needed.