Sliding Window Template
Sliding window is the linear-time alternative to nested loops for substring-and-subarray problems. This snippet covers the fixed-size window for max-sum-of-k, the variable-size window for longest-substring-with-condition, and the at-most-K shrinkable form that handles 'at most / exactly K distinct' problems with one trick.
995 views
12
function maxSumK(arr, k) {
if (arr.length < k) return null;
let sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
let best = sum;
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
if (sum > best) best = sum;
}
return best;
}
console.log(maxSumK([2, 1, 5, 1, 3, 2], 3)); // 9 (5 + 1 + 3)
console.log(maxSumK([1, 2, 3], 5)); // nullWhen the window size is fixed, the trick is to compute the first window's sum once and then slide it by adding the new element and removing the old one (sum += arr[i] - arr[i - k]). This O(n) update replaces the O(n*k) recomputation a naive solution would do. The same skeleton handles fixed-size averages, max-of-k, and any aggregate that supports incremental update. The early-return when the array is shorter than k is the easy edge case to forget.
function longestUniqueSubstring(s) {
const seen = new Map();
let lo = 0;
let best = 0;
for (let hi = 0; hi < s.length; hi++) {
const ch = s[hi];
if (seen.has(ch) && seen.get(ch) >= lo) {
lo = seen.get(ch) + 1;
}
seen.set(ch, hi);
if (hi - lo + 1 > best) best = hi - lo + 1;
}
return best;
}
console.log(longestUniqueSubstring('abcabcbb')); // 3 (abc)
console.log(longestUniqueSubstring('bbbbb')); // 1
console.log(longestUniqueSubstring('')); // 0When the window size depends on the data (longest valid substring, smallest window covering a target), use two pointers and a hash structure. The right pointer extends while the window stays valid, and the left pointer jumps past the offending position when validity breaks. Storing the last index where each character appeared lets the left pointer leap rather than slide one-by-one, keeping the whole pass O(n). This is LeetCode's longest-substring-without-repeat in 10 lines.
function atMostK(s, k) {
const counts = new Map();
let lo = 0;
let total = 0;
let distinct = 0;
for (let hi = 0; hi < s.length; hi++) {
if ((counts.get(s[hi]) || 0) === 0) distinct++;
counts.set(s[hi], (counts.get(s[hi]) || 0) + 1);
while (distinct > k) {
counts.set(s[lo], counts.get(s[lo]) - 1);
if (counts.get(s[lo]) === 0) distinct--;
lo++;
}
total += hi - lo + 1;
}
return total;
}
function exactlyK(s, k) {
return atMostK(s, k) - atMostK(s, k - 1);
}
console.log(atMostK('eceba', 2)); // 10
console.log(exactlyK('eceba', 2)); // 5Counting subarrays with 'exactly K distinct' values is hard, but counting 'at most K' is straightforward with sliding window. The trick: exactly(K) === atMost(K) - atMost(K - 1). The at-most function counts subarrays ending at each position by accumulating hi - lo + 1, which works because every shorter window starting in [lo, hi] is also valid. This decomposition turns several otherwise tricky problems (subarrays-with-K-different-integers, count-vowel-strings) into two calls of the same templated function.