Sliding Window — Longest/Shortest Substring Problems

Any problem asking about a contiguous chunk — "longest substring with…", "smallest subarray that…" — is a sliding window problem. It turns "check every substring" O(n²)/O(n³) into a single O(n) pass.

The idea

Maintain a window [left…right] over the data. Grow it by moving right; when the window breaks the rule, shrink from left until it's valid again. Every element enters and leaves the window at most once → O(n).

The variable-window template (memorise this shape)

// Longest substring without repeating characters
function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, best = 0;

  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {     // window invalid?
      seen.delete(s[left]);          // shrink from the left
      left++;
    }
    seen.add(s[right]);              // grow
    best = Math.max(best, right - left + 1);
  }
  return best;
}

The rhythm: for-loop grows right → while-loop shrinks left → record the answer. Nearly every window problem is this skeleton with a different "invalid" condition and a different bookkeeping structure (Set, Map of counts, running sum).

Fixed-size windows

"Max sum of any subarray of size K" — slide a window of exactly K: add the entering element, subtract the leaving one. No recomputing the whole sum.

let sum = 0, best = -Infinity;
for (let i = 0; i < nums.length; i++) {
  sum += nums[i];                       // enter
  if (i >= k - 1) {
    best = Math.max(best, sum);
    sum -= nums[i - k + 1];             // leave
  }
}

Spot it when…

• The word substring / subarray (contiguous!) appears with longest / shortest / max / count.
• Constraints involve "at most K distinct", "no repeats", "sum ≥ target".

Practice now

• Longest Substring Without Repeats — the classic above, with hidden tests
• Maximum Subarray — related; contrast with Kadane's

Trap to name in interviews: sliding window needs contiguity. "Longest subsequence" (non-contiguous) is a different pattern — usually DP.