Longest Substring Without Repeating Characters
Variable window plus the last index of each character; a repeat inside jumps the left edge past its earlier copy.
Decision · step 2 of 10Substring Windows: Longest run without a repeat
r = 0, 'a'. Not in the window, so it simply joins. Window "a" of length 1, a new best.
What you will see
A repeat entering from the right pushes the left edge past the earlier copy.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(alphabet) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Cells announce index, value and whether they are inside the window; each step announces the window bounds and the running value.
Reduced motion: The window frame snaps to its new bounds with a crossfade.
Before this
Taught by the same lesson
Substring Windows covers these too, in the same run.