Longest Substring Without Repeating Characters
The problem
Return the length of the longest contiguous substring whose characters are all distinct.
Example
"abcaef" → 5, from "bcaef"
Need a hint?
When a duplicate arrives, jump past its last occurrence.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Keep a window start and a map from character to most recent index. For each character at right, set start to the larger of its current value and last occurrence + 1. Record the new occurrence and maximize right − start + 1. The maximum prevents moving the start backward.
Complexity
O(n) expected time and O(min(n, alphabet size)) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.