128. No-Repeat Stretch
A text editor highlights the longest stretch of characters in which no character appears twice. Given the string s, find the length of the longest substring, that is, a run of consecutive characters, that contains no repeated character. Spaces and punctuation count as characters, and upper case and lower case letters are different characters.
Return that length. A substring must be contiguous, so choosing separate letters from different places does not count. A sliding window with a table of last positions solves the task in linear time; checking every substring is far too slow for long texts.
Example 1
- Input:
- s = "abcabcdd"
- Output:
- 4
- Explanation:
The longest repeat-free stretch is abcd, which has length 4.
Example 2
- Input:
- s = "zzzz"
- Output:
- 1
- Explanation:
Every stretch of length two repeats the letter z, so the best length is 1.
Constraints
1 ≤ s.length ≤ 105
s contains printable ASCII characters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)