Longest Repeat-Free Stretch
MediumSliding Window
Problem
A keystroke logger records a string s. Find the longest contiguous stretch of s in which no character occurs twice, and return its length.
Characters are any printable ASCII symbols, including spaces and digits.
Example 1
- Input:
- s = "abcbdefb"
- Output:
- 5
The stretch "cbdef" has five different characters; extending it either way repeats a "b".
Example 2
- Input:
- s = "zzzz"
- Output:
- 1
Example 3
- Input:
- s = ""
- Output:
- 0
Constraints
- 0 ≤ s.length ≤ 10^5
- s consists of printable ASCII characters.
Hint
Show the first hint
If s[l..r] has no repeats, so does every stretch inside it. Can you grow a window on the right and only shrink it when forced?
Walkthrough
How to approach it
01Clarify before coding
- Is the comparison case-sensitive? Yes, 'a' and 'A' are different characters.
- Do spaces and punctuation count as characters? Yes.
- Substring or subsequence? Substring: contiguous.
02Brute force
Try every start l, extend r while the characters stay unique (using a set), and record the longest.
Cost: O(n·m) time where m is the alphabet size (each extension stops after at most m steps); with a naive recheck per substring it is O(n³).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.