Given the string "abcabcbb", find the length of the longest substring where no character repeats. The brute force is simple: start at each index, expand until you hit a duplicate, record the length, move to the next index. But something wasteful hides inside that loop. Watch the animation below and see if you can spot it.
The brute force approach starts at each index, expands until a duplicate appears, then moves to the next index. Each run builds a fresh set of unique characters from scratch. Think about what happens when consecutive runs overlap — when the second run starts at index 1, it checks characters that the first run already proved were unique.
The brute force tries 3 starting positions on "abcabcbb". Each run expands until it hits a duplicate. How many character checks will be wasted re-validating characters that a previous run already confirmed unique?
Run 1: starting at index 0