Sliding Window
Maintain a window over a sequence and slide it forward one element at a time — adding to the right, removing from the left. Converts O(n²) subarray problems to O(n).
The Pattern
A sliding window is a subarray or substring that moves forward through a sequence by adding one element to its right edge and (sometimes) removing one from its left edge. The window avoids recomputing from scratch at each position by maintaining a running state — a sum, a frequency map, a count of bad elements — and updating it incrementally.
There are two variants. A fixed-size window always has exactly k elements: when moving right by one, the element at i - k leaves and arr[i] enters. A variable-size window expands when a condition is still satisfied and contracts from the left when it is violated. The variable window is more powerful: it finds the minimum or maximum window that meets a constraint.
Fixed Window — Maximum Sum of Size k
The naive approach recomputes the sum of each k-length window from scratch: O(n·k). The sliding window subtracts the outgoing element and adds the incoming element each step, keeping the sum current in O(1) per step and O(n) total.
fn max_sum_k(arr: &[i32], k: usize) -> Option<i32> {
if arr.len() < k { return None; }
let mut window: i32 = arr[..k].iter().sum();
let mut best = window;
for i in k..arr.len() {
window += arr[i] - arr[i - k];
best = best.max(window);
}
Some(best)
}
fn main() {
println!("{:?}", max_sum_k(&[2,1,5,1,3,2], 3)); // Some(9) [5,1,3]
println!("{:?}", max_sum_k(&[2,3,4,1,5], 2)); // Some(7) [3,4]
}Variable Window — Longest Substring Without Repeating Characters
Expand the right pointer to add characters. When a duplicate is found, shrink from the left until the window has no duplicates again. A frequency map tracks counts; contracting stops when the duplicate count drops to one.
use std::collections::HashMap;
fn length_of_longest_substring(s: &str) -> usize {
let chars: Vec<char> = s.chars().collect();
let mut freq: HashMap<char, usize> = HashMap::new();
let mut left = 0;
let mut best = 0;
for right in 0..chars.len() {
*freq.entry(chars[right]).or_insert(0) += 1;
// Shrink window while duplicate exists
while freq[&chars[right]] > 1 {
*freq.get_mut(&chars[left]).unwrap() -= 1;
left += 1;
}
best = best.max(right - left + 1);
}
best
}
fn main() {
println!("{}", length_of_longest_substring("abcabcbb")); // 3 "abc"
println!("{}", length_of_longest_substring("bbbbb")); // 1 "b"
println!("{}", length_of_longest_substring("pwwkew")); // 3 "wke"
}Variable Window — Minimum Window Substring
Find the smallest window in s that contains all characters of t. Expand right to include needed characters. Once all characters are covered (all required counts are met), try to shrink from the left. Record the window size at each valid state and advance left.
use std::collections::HashMap;
fn min_window(s: &str, t: &str) -> String {
let s: Vec<char> = s.chars().collect();
let mut need: HashMap<char, i32> = HashMap::new();
for c in t.chars() { *need.entry(c).or_insert(0) += 1; }
let required = need.len();
let mut have = 0;
let mut window: HashMap<char, i32> = HashMap::new();
let mut best = (usize::MAX, 0, 0); // (length, left, right)
let mut left = 0;
for right in 0..s.len() {
let c = s[right];
*window.entry(c).or_insert(0) += 1;
if let Some(&needed) = need.get(&c) {
if window[&c] == needed { have += 1; }
}
while have == required {
let len = right - left + 1;
if len < best.0 { best = (len, left, right); }
let lc = s[left];
*window.get_mut(&lc).unwrap() -= 1;
if let Some(&needed) = need.get(&lc) {
if window[&lc] < needed { have -= 1; }
}
left += 1;
}
}
if best.0 == usize::MAX { String::new() }
else { s[best.1..=best.2].iter().collect() }
}
fn main() {
println!("{}", min_window("ADOBECODEBANC", "ABC")); // "BANC"
println!("{}", min_window("a", "a")); // "a"
println!("{}", min_window("a", "aa")); // ""
}Variable Window — Longest Subarray with At Most K Zeros
Find the longest subarray of 1s after replacing at most k zeros. Expand right always; shrink left when the window has more than k zeros. The window variable tracks the current count of zeros.
fn longest_ones(nums: &[i32], k: i32) -> usize {
let (mut left, mut zeros) = (0usize, 0i32);
let mut best = 0;
for right in 0..nums.len() {
if nums[right] == 0 { zeros += 1; }
while zeros > k {
if nums[left] == 0 { zeros -= 1; }
left += 1;
}
best = best.max(right - left + 1);
}
best
}
fn main() {
println!("{}", longest_ones(&[1,1,1,0,0,0,1,1,1,1,0], 2)); // 6
println!("{}", longest_ones(&[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3)); // 10
}Fixed Window — Find All Anagrams
Find all start indices of anagrams of p in s. Maintain a frequency window of size p.len() over s. Compare the window's character counts to p's counts. Use a "matches" counter to avoid comparing the entire map each step: increment matches when a character's count in the window reaches the required count, decrement when it drops below.
fn find_anagrams(s: &str, p: &str) -> Vec<usize> {
let s: Vec<u8> = s.bytes().collect();
let p: Vec<u8> = p.bytes().collect();
if s.len() < p.len() { return vec![]; }
let mut p_count = [0i32; 26];
let mut w_count = [0i32; 26];
for &b in &p { p_count[(b - b'a') as usize] += 1; }
let k = p.len();
let mut matches = 0usize;
let total = p_count.iter().filter(|&&c| c > 0).count();
let mut result = Vec::new();
for i in 0..s.len() {
let c = (s[i] - b'a') as usize;
w_count[c] += 1;
if w_count[c] == p_count[c] { matches += 1; }
if i >= k {
let out = (s[i - k] - b'a') as usize;
if w_count[out] == p_count[out] { matches -= 1; }
w_count[out] -= 1;
}
if matches == total { result.push(i + 1 - k); }
}
result
}
fn main() {
println!("{:?}", find_anagrams("cbaebabacd", "abc")); // [0, 6]
println!("{:?}", find_anagrams("abab", "ab")); // [0, 1, 2]
}Variable Window — Subarray Product Less Than K
Count subarrays whose product is strictly less than k. Maintain a window with a running product. Expand right; when the product exceeds k, shrink left until it is valid again. Every right-ending window that satisfies the constraint contributes exactly right - left + 1 valid subarrays (all subarrays ending at right with left as the minimum valid start).
fn num_subarrays_product_less_than_k(nums: &[i32], k: i32) -> usize {
if k <= 1 { return 0; }
let (mut left, mut product, mut count) = (0usize, 1i32, 0usize);
for right in 0..nums.len() {
product *= nums[right];
while product >= k {
product /= nums[left];
left += 1;
}
count += right - left + 1;
}
count
}
fn main() {
println!("{}", num_subarrays_product_less_than_k(&[10,5,2,6], 100)); // 8
println!("{}", num_subarrays_product_less_than_k(&[1,2,3], 0)); // 0
}