The sliding window pattern, once and for all

Half the medium-difficulty array problems on LeetCode are the same problem wearing different costumes: find the best contiguous chunk that satisfies a condition. Longest substring without repeats, max sum subarray of size k, smallest subarray with sum ≥ target — all of them.

The costume changes; the pattern doesn't.

How to recognize it

Ask three questions:

1. Is the input a sequence (array/string)?
2. Am I looking for a contiguous window (substring/subarray)?
3. Is there a condition that makes a window valid or invalid?

Three yeses → sliding window. The brute force is O(n²) (try every window); the pattern makes it O(n) because each pointer only ever moves forward.

The template

function slidingWindow(s: string): number {
  const state = new Map<string, number>(); // whatever the window needs to track
  let left = 0;
  let best = 0;
 
  for (let right = 0; right < s.length; right++) {
    // 1. bring s[right] into the window
    state.set(s[right], (state.get(s[right]) ?? 0) + 1);
 
    // 2. shrink from the left until the window is valid again
    while (windowIsInvalid(state)) {
      state.set(s[left], state.get(s[left])! - 1);
      left++;
    }
 
    // 3. the window [left, right] is valid — record it
    best = Math.max(best, right - left + 1);
  }
  return best;
}

The only things that change between problems are the state you track and the definition of windowIsInvalid.

Example: longest substring without repeating characters

State = character counts. Invalid = any count above 1.

function lengthOfLongestSubstring(s: string): number {
  const count = new Map<string, number>();
  let left = 0, best = 0;
 
  for (let right = 0; right < s.length; right++) {
    count.set(s[right], (count.get(s[right]) ?? 0) + 1);
    while (count.get(s[right])! > 1) {
      count.set(s[left], count.get(s[left])! - 1);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

"abcabcbb" → 3 ("abc"). Each character enters the window once and leaves at most once — that's the O(n).

The one gotcha

Fixed-size windows (e.g. "max sum of subarray of size k") are simpler: no while loop, just slide both ends together once the window reaches size k. If you find yourself writing a while loop for a fixed-size window, you've overcomplicated it.

I keep this template saved as a gist and re-derive the state/invalid-condition per problem. It has yet to let me down.