Longest Stretch Without a Repeat

Problem Statement

You're given a single line of lowercase letters. Find the length of the longest contiguous stretch of that line in which no letter repeats. The line can be empty, in which case the longest such stretch has length 0.

Input Format

The input is exactly one line containing zero or more lowercase English letters (a-z), with no spaces or other characters. The line may be empty.

Output Format

Print a single integer: the length of the longest contiguous stretch of the input that contains no repeated letter.

Example Walkthrough

Take the first sample, abcabcbb. Picture a window that starts at index 0 and grows to the right one letter at a time, while a dictionary remembers the most recent index at which each letter was seen. Starting with an empty window, we add a (index 0), b (index 1), and c (index 2) — none of these repeat anything already in the window, so the window is now abc, length 3. At index 3 we see a again; it was last seen at index 0, which is still inside the current window (which starts at index 0), so the window's left edge has to move to index 1, just past that earlier a. The window is now bca (indices 1-3), still length 3. Continuing this way — sliding the window forward and shrinking it from the left only when a repeat would otherwise occur inside it — the window's length never exceeds 3 for the rest of the string, even though the string keeps going. The longest window seen at any point was length 3, so that's the answer.

Approach

The brute-force way to solve this is to check every possible starting position, and for each one scan forward collecting letters into a set until a repeat is found, recording the longest stretch seen. This works, but for a string of length n it can re-scan overlapping stretches of the string over and over, costing O(n²) time in the worst case (for example, on a string with no repeats at all, every starting position scans almost the whole rest of the string).

A sliding window avoids that repeated work. Keep two indices, start and i, marking the current window s[start:i+1], and a dictionary that maps each letter to the most recent index where it appeared. Move i forward one letter at a time. Before adding s[i] to the window, check the dictionary: if s[i] was seen before and that earlier occurrence is at or after start (meaning it's still inside the current window), the window can no longer contain both occurrences without a repeat, so move start to one past that earlier occurrence. Either way, update the dictionary with s[i]'s new index, and compare the window's current length (i - start + 1) against the best length seen so far.

The key reason this is only O(n) total, rather than O(n²), is that start only ever moves forward and never backward — across the whole scan, start advances at most n times in total, the same as i. Neither index ever revisits ground it has already covered, so the window slides across the string in a single pass instead of restarting from scratch at every position.

Common Mistakes

• Moving start backward, or resetting it to 0, whenever a repeat is found. The window should only ever shrink from the left by moving start forward — jumping it back to an earlier position (or all the way to 0) throws away progress and can even make the window's reported length wrong, since start no longer marks a window boundary the letters actually respect.
• Shrinking the window on any repeat found anywhere in the letter's history, even outside the current window. If a letter's last recorded index is before start (it fell out of the window on an earlier step), it's no longer actually inside the window and doesn't force a shrink. Moving start forward anyway in that case can push it past letters that are still perfectly valid to keep, undercounting the true longest stretch.
• Forgetting the empty-string case. With no letters to scan at all, the loop body never runs, and the answer should come out to 0 automatically as long as the "best length so far" starts at 0 rather than being left uninitialized or defaulting to something else.