sliding-window • Intermediate

Sliding Window Technique: Fixed vs Dynamic Windows

A sliding window maintains a contiguous subarray [left, right], incrementally adding elements at the right boundary and removing elements at the left boundary in linear O(N) time.

Intuitive Mental Model

The Magnifying Glass on a Sentence: You slide a magnifying glass of width K along a text line. As new letters enter on the right, old letters leave on the left, keeping track of letter frequencies with zero re-scanning.

C / TypeScript ImplementationHardware & Algorithmic Standard

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

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    if (seen.has(char) && seen.get(char)! >= left) {
      left = seen.get(char)! + 1;
    }
    seen.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Key Architectural Takeaways

•Avoids O(N^2) Recomputation: Calculates running window state incrementally in O(1) per step.
•Fixed Window: Window size K remains constant.
•Dynamic Window: Expands on right and contracts on left to maintain validity.

Common Coding Mistake

Re-evaluating the entire window content on every iteration with a nested loop.

Optimal Solution

Update the window state incrementally in O(1).

Next: Prefix Sums & O(1) Range Queries