Longest stretch with no repeats
MediumStuck?
Show a hintHide the hint
Grow a window to the right. When a letter repeats, move the left edge to just past where that letter last appeared.
The ideas behind this problem
Next in this lesson
Best run after k changesFind the length of the longest stretch of a word that contains no repeated letter.
Worked example#
For abcabcbb, keep a window that is allowed to grow on the right and must shrink from the left whenever a letter repeats:
| step | window | note |
|---|---|---|
| a | a | length 1 |
| b | ab | length 2 |
| c | abc | length 3, the best so far |
| a | bca | the a repeated, so the left edge moves past the old a |
| b | cab | the b repeated, left edge moves again |
| c | abc | length 3 again |
| b | cb | |
| b | b |
The longest the window ever got was 3, so the answer is 3.
The important part is what happens on a repeat: the left edge jumps to just past the previous position of that letter. It never moves backwards, so each letter is visited at most twice, once by each edge. That is what makes this one pass rather than checking every stretch.
Constraints#
0 <= length <= 100000- Lowercase letters only
Input
s is one word.
Output
The length of the longest stretch with no repeated letter.
Examples
Input
abcabcbb
Output
3
abc is the longest stretch before a letter repeats.
Input
bbbbb
Output
1
Every letter is the same, so no stretch longer than one works.
Input
pwwkew
Output
3
wke is three long. pwke is not a stretch, because it skips a letter.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.