Hone

Lessons · TypeScript · the sliding window

A window that grows and shrinks

Keep a start and an end over the same sequence. The end always moves forward; the start moves forward only when the window has broken a rule.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

It answers almost every question about the best CONTIGUOUS run: the longest stretch without a repeat, the smallest stretch containing everything, the best sum of any k in a row.

How to think about it

Look for 'contiguous', a substring, or 'in a row'. Name the rule the window must obey, move the end one item at a time, and while the rule is broken move the start.

Worked example

function longestRunWithoutRepeat(text) {
  const lastSeen = new Map();
Where each character was last seen.
  let start = 0, best = 0;
The window start, and the answer.
  for (let end = 0; end < text.length; end++) {
The end moves forward, once per character.
    const ch = text[end];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= start) start = lastSeen.get(ch) + 1;
Jump the start past the repeat. Never backwards.
    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
The window is end - start + 1 wide.
  }
  return best;
}
console.log(longestRunWithoutRepeat('abcabcbb'));
3
console.log(longestRunWithoutRepeat('bbbbb'));
1
console.log(longestRunWithoutRepeat(''));
0

Your turn

Shrink the window past the repeated character.

if (lastSeen.has(ch) && lastSeen.get(ch) >= start) {
  start = lastSeen.(ch) + 1;
}

The trap

It looks like a nested loop and is not. Each end moves forward at most n times across the whole run, so the total is one pass, not n squared.

Practise the sliding window on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.