Longest stretch with no repeat
A token generator checks its output for the longest run of characters in which nothing appears twice.
- The run has to be a single unbroken stretch, not a selection.
- Every character counts, including spaces and punctuation.
- Empty text has a longest run of zero.
longestUniqueRun(text: string) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func longestUniqueRun(text string) int {
}Worked examples
| Call | Result |
|---|---|
longestUniqueRun("abcabcbb") | 3 |
longestUniqueRun("bbbbb") | 1 |
longestUniqueRun("pwwkew") | 3 |
longestUniqueRun("abcdef") | 6 |
Hint
Slide a window. When a repeat comes in, pull the left edge past where that character was last seen — never backwards.
Reference solution in Go
func longestUniqueRun(text string) int {
lastAt := map[byte]int{}
best, start := 0, 0
for i := 0; i < len(text); i++ {
c := text[i]
if seen, ok := lastAt[c]; ok && seen >= start {
start = seen + 1
}
lastAt[c] = i
if i-start+1 > best {
best = i - start + 1
}
}
return best
}