Sliding Window

Take the word abcabcbb. Find the longest stretch of it with no repeated letter.

Read it yourself first. abc works — three letters, all different. Adding the next a would repeat, so three is as far as that stretch goes. The answer turns out to be 3, and there are several stretches that long.

The obvious way is very slow

Check every possible stretch, and for each one check whether it has duplicates:

for (let i = 0; i < text.length; i++) {
  for (let j = i; j < text.length; j++) {
    if (allUnique(text.slice(i, j + 1))) best = Math.max(best, j - i + 1);
  }
}

Two loops to pick the start and end, and allUnique walks the stretch again — that is three levels of work, $O(n^3)$. For a problem you just solved by eye.

The realisation

You never need to start over.

When the window becomes invalid — a repeat appears — the fix is always to pull the left edge in. You never have to move the right edge back and re-examine letters you have already passed.

Watch the left edge jump when a repeat shows up:

for (let end = 0; end < text.length; end++) {  const seen = lastSeen.get(text[end]);   if (seen !== undefined && seen >= start) start = seen + 1;   lastSeen.set(text[end], end);  best = Math.max(best, end - start + 1);}

Why this is fast

Both edges only ever move right. end advances once per letter, and start never goes backwards. Between them they take at most $2n$ steps.

$O(n^3)$ down to $O(n)$. For a 10,000-character string, that is a trillion operations down to twenty thousand.

The code

function longestUnique(text: string): number {
  const lastSeen = new Map<string, number>();
  let best = 0;
  let start = 0;

  for (let end = 0; end < text.length; end += 1) {
    const ch = text[end]!;
    const previous = lastSeen.get(ch);

    // Only jump forwards. An index from before `start` is not a duplicate
    // inside the current window — it is already outside it.
    if (previous !== undefined && previous >= start) start = previous + 1;

    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
  }

  return best;
}

That previous >= start check is easy to leave out. Without it, an old sighting from outside the window drags start backwards, and the window starts growing and shrinking unpredictably.

Two shapes, and the one that trips people

A fixed window has a set size. Add the incoming element, remove the outgoing one, and the size never changes:

sum += values[i];
if (i >= k) sum -= values[i - k];   // exactly one leaves

A variable window grows until it breaks a rule, then shrinks until it is legal again.

When it does not work

The window only works if the rule is monotone: once adding something breaks it, adding more cannot fix it.

“Sum at most 10” over positive numbers is monotone — the sum only grows, so shrinking from the left is the only cure.

Add negative numbers and it stops being true. A later -5 could bring the sum back under 10, so a window you rejected might have been fine after all. Shrinking from the left is no longer justified, and you need prefix sums instead.

That is the same shape of precondition as sortedness in two pointers: a simple loop, made correct by a property of the data rather than by anything in the code.