How does the sliding window technique work?

The window is defined by a left and right boundary. The right boundary expands the window, and the left boundary contracts it when the window becomes invalid. You maintain summary state, such as a sum or a frequency map, instead of recomputing from scratch.

function longestUnique(text) {
  const lastSeen = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < text.length; right++) {
    const ch = text[right];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1;
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Two window shapes

• Fixed-size window: add the new element and remove the element that leaves
• Variable-size window: expand until invalid, then shrink until valid again
• Maintain a count, sum or frequency map instead of rescanning the window
• Be careful when the validity condition can change in both directions

The complexity argument is important. Even though there is an inner while loop, each element is added at most once and removed at most once, so the total work is O(n). Say that explicitly rather than claiming the inner loop makes it O(n^2).