AlgoScope

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.

Sliding window, algorithm, intermediate
Right 0 is a. Window from 0 to 0, length 1.window 0-0best 0-0a0b1c2a3b4c5b6b7lr
Right 0 is a. Window from 0 to 0, length 1.window 0-0best 0-0a0b1c2a3b4c5b6b7lr

Substring Windows: Longest run without a repeat

Decision, step 2 of 10

r = 0, 'a'. Not in the window, so it simply joins. Window "a" of length 1, a new best.

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(alphabet)

Taught by the same lesson

Substring Windows covers these too, in the same run.