The Longest Stretch of New Faces

A security camera writes down one letter for each person entering a hall, the same letter for the same person. The guard wants the longest continuous stretch in which nobody repeats — a stretch in which every entry is a different person.

Return the length of that longest stretch.

Examples

Example 1

Input:  log = "abcabcbb"
Output: 3

Reading "abcabcbb": abc is fine, but the next a repeats the first one, so the window slides to bca, then cab, then abc again. Every time a repeat appears the window shrinks, and no window ever holds 4 different letters, so the answer is 3.

Example 2

Input:  log = "bbbbb"
Output: 1

Example 3

Input:  log = "abcde"
Output: 5

Constraints

log is 1 to 100,000 lowercase letters.

The stretch must be continuous. "abcabcbb" has a longest stretch of 3 (abc), not 4.

How to solve it

Hint

Grow a window to the right; when the new letter is already inside the window, jump the window’s left edge past its previous position.

Approach: Variable sliding window with last-seen positions

Remember, for every letter, the position where you last saw it.
Walk the right edge of the window forward one letter at a time.
If that letter was last seen at or after the window’s left edge, move the left edge to just past it, then update the best length.

Check with the example. In “abcabcbb” the windows abc, bca, cab all reach 3, and nothing reaches 4.

Complexity: O(n) time, O(1) space (26 positions).

The reference solutions in all four languages are in the Solutions tab of the workspace below.