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
C++ 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
int longestUniqueRun(std::string text) {
}Worked examples
| Call | Result |
|---|---|
longestUniqueRun(std::string("abcabcbb")) | 3 |
longestUniqueRun(std::string("bbbbb")) | 1 |
longestUniqueRun(std::string("pwwkew")) | 3 |
longestUniqueRun(std::string("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 C++
int longestUniqueRun(std::string text) {
std::map<char, int> lastAt;
int best = 0, start = 0;
for (int i = 0; i < (int) text.size(); i++) {
char c = text[i];
auto it = lastAt.find(c);
if (it != lastAt.end() && it->second >= start) start = it->second + 1;
lastAt[c] = i;
best = std::max(best, i - start + 1);
}
return best;
}