Fixed-size and variable-size window techniques for substring and subarray problems -- templates that turn O(n^2) into O(n)

Sliding Window

Sliding window maintains a "window" over a contiguous portion of an array or string and slides it across the input. Instead of recalculating everything from scratch for each position, you incrementally update the window state. This turns many O(n^2) brute-force approaches into O(n).

Two main variants:

Fixed-size window -- window length is known upfront
Variable-size window -- window grows and shrinks based on a condition

Fixed-Size Window

The window size k is given. Slide it across, maintaining a running computation.

Max Sum Subarray of Size K

function maxSumSubarray(nums: number[], k: number): number {
  let windowSum = 0;
  let maxSum = -Infinity;

  for (let i = 0; i < nums.length; i++) {
    windowSum += nums[i]; // expand window

    if (i >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= nums[i - k + 1]; // shrink window
    }
  }

  return maxSum;
}

Time: O(n), Space: O(1). Without the sliding window, you would sum k elements for each of n positions: O(nk).

Fixed Window Template

function fixedWindow(arr: number[], k: number): void {
  // Initialize window state for first k elements
  let state = 0;
  for (let i = 0; i < k; i++) {
    state += arr[i]; // or whatever accumulation you need
  }

  // Process first window
  // ...

  // Slide the window
  for (let i = k; i < arr.length; i++) {
    state += arr[i];       // add new element entering window
    state -= arr[i - k];   // remove element leaving window
    // Process current window
  }
}

Variable-Size Window

The window size is not fixed. You expand by moving the right pointer, and shrink by moving the left pointer when the window violates some constraint. This is the more common and trickier variant.

The Shrinkable Window Template

This template works for most variable-size window problems:

function variableWindow(s: string): number {
  let left = 0;
  let result = 0;
  // Window state (map, set, counter, etc.)

  for (let right = 0; right < s.length; right++) {
    // 1. Expand: add s[right] to window state

    // 2. Shrink: while window is invalid, remove s[left]
    while (/* window is invalid */) {
      // remove s[left] from window state
      left++;
    }

    // 3. Update result (window [left..right] is valid)
    result = Math.max(result, right - left + 1);
  }

  return result;
}

The key insight: the right pointer moves forward one step at a time. When the window becomes invalid, the left pointer advances until it is valid again. Both pointers only move forward, so the total work is O(n).

Longest Substring Without Repeating Characters

Find the length of the longest substring with all unique characters.

function lengthOfLongestSubstring(s: string): number {
  const charIndex = new Map<string, number>();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    // If char is in the window, jump left past its previous position
    if (charIndex.has(char) && charIndex.get(char)! >= left) {
      left = charIndex.get(char)! + 1;
    }

    charIndex.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

Time: O(n), Space: O(min(n, alphabet size)).

Minimum Window Substring

Find the shortest substring of s that contains all characters of t.

function minWindow(s: string, t: string): string {
  if (t.length > s.length) return "";

  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
  }

  let have = 0;
  const required = need.size; // number of unique chars needed
  const windowCount = new Map<string, number>();

  let left = 0;
  let minLen = Infinity;
  let minStart = 0;

  for (let right = 0; right < s.length; right++) {
    // Expand
    const char = s[right];
    windowCount.set(char, (windowCount.get(char) ?? 0) + 1);

    if (need.has(char) && windowCount.get(char) === need.get(char)) {
      have++;
    }

    // Shrink while valid
    while (have === required) {
      // Update result
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }

      // Remove left char
      const leftChar = s[left];
      windowCount.set(leftChar, windowCount.get(leftChar)! - 1);
      if (need.has(leftChar) && windowCount.get(leftChar)! < need.get(leftChar)!) {
        have--;
      }
      left++;
    }
  }

  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

Time: O(n + m) where n = |s|, m = |t|. Space: O(alphabet size).

This problem flips the template slightly: we shrink while the window is valid (because we want the minimum valid window), and update the result inside the shrink loop.

Maximum Consecutive Ones III

Given a binary array, find the longest subarray of 1s if you can flip at most k zeros.

function longestOnes(nums: number[], k: number): number {
  let left = 0;
  let zeros = 0;
  let maxLen = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++;

    while (zeros > k) {
      if (nums[left] === 0) zeros--;
      left++;
    }

    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

Time: O(n), Space: O(1).

Choosing Minimum vs Maximum

The update-result placement depends on what you are optimizing:

Longest/maximum valid window: shrink while invalid, update result after the shrink loop (the window is now valid and as large as possible).
Shortest/minimum valid window: shrink while valid, update result inside the shrink loop (each valid window is a candidate).

// Finding LONGEST valid window
for (let right = 0; right < n; right++) {
  // expand
  while (/* invalid */) { left++; /* shrink */ }
  result = Math.max(result, right - left + 1); // after shrink
}

// Finding SHORTEST valid window
for (let right = 0; right < n; right++) {
  // expand
  while (/* valid */) {
    result = Math.min(result, right - left + 1); // inside shrink
    left++; // shrink
  }
}

Common Mistakes

Off-by-one in window size. The window [left, right] has size right - left + 1. Double-check this.
Forgetting to update state when shrinking. Whatever you add when expanding, you must undo when shrinking.
Using a set when you need a map. If the input has duplicate characters and you need to track counts, a set is not enough.
Not handling the empty input. Always check edge cases: empty string, k = 0, window larger than input.

When to Use Sliding Window

The problem asks about contiguous subarrays or substrings
You need to find something minimum or maximum within a contiguous range
There is a constraint that defines window validity (sum, unique chars, frequency)
The brute force is "check every subarray" at O(n^2) or worse

Complexity Summary

Problem	Time	Space
Max sum subarray of size K	O(n)	O(1)
Longest substring without repeats	O(n)	O(min(n, alphabet))
Minimum window substring	O(n + m)	O(alphabet)
Max consecutive ones with K flips	O(n)	O(1)

Sliding window is the go-to technique whenever you see "contiguous subarray" or "substring" in a problem statement. Learn the two templates -- fixed and variable -- and most problems become straightforward applications.

Sliding Window

On this page