Find the longest stretch of a word in which no character repeats.
What to build
A sliding window whose left edge jumps forward when needed.
Requirements
- Read a word.
- Print the length of the longest stretch of neighbouring characters with no repeats.
Input
One word.
Output
One number.
Constraints
The word has from 1 to 100000 lowercase letters.
Example
Input:
abcabcbb
Output:
3
Why it works
The right edge only moves forward, and the left edge never goes back, so the whole word takes one pass, even though many stretches are being considered.
Examples
Example 1 · Input
abcabcbb
Expected output
3
Example 2 · Input
bbbb
Expected output
1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Grow the window on the right, one character at a time.
Hint 2
Remember the last position where each character was seen.
Hint 3
If a character repeats inside the window, move the left edge just past its last position.
Solution
Show one correct solution (try it yourself first)
word = input()
last = {}
left = 0
best = 0
for right, ch in enumerate(word):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
print(best)