Jump past the repeat
The longest stretch of text with no repeated character. About 10 minutes.
A window with no repeats
A password rule says: find the longest stretch of characters where nothing repeats. The sliding window from Arrays works on text too. Grow the window on the right one character at a time. The rule for a good window is "no character appears twice".
When the new character is already inside the window, the window has to give up everything up to and including that earlier copy.
- best
- 3
- last
- {a: 0, b: 1, c: 2}
Grow right: a, b, c. No repeats yet, window length 3.
Jump instead of crawling
You could shrink one character at a time until the repeat is gone, but there's a shortcut. Remember where each character was last seen. When it repeats, move the window's left end straight to just after that last sighting, in one jump.
One catch: an old sighting from before the window's left end doesn't count, because that copy isn't in the window any more.
last = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return bestIn "abcab", the window holds "bca" (boxes 1 to 3). The next character is a b, in box 4. Where does the left end jump to?
- ABox 2
- BBox 4
- CIt stays at box 1
Show the answer
Box 2. The earlier b is in box 1, inside the window, so the left end jumps to just after it: "cab".
Longest stretch without repeats
You get a string. Return the length of the longest run of consecutive characters in which no character appears twice.
s = "abcabcbb" → 3
0 ≤ length ≤ 100,000 · printable ASCII characters