JuniorCodeOccasionalNot answered yet
Length of the longest run of identical characters
Given a lowercase string s, return the length of the longest substring whose characters are all identical. The empty string returns 0.
Requirements:
each index".
- O(n) time, O(1) extra space — a single pass, not the O(n²) "scan right from
int longestRun(const std::string& s) {
// your code here
}Write the implementation.
Sweep once with a current run length. While the next character equals the current one, extend the run; on a change, reset to 1. Track the maximum run length across the pass. One pass, O(n) time, O(1) space; the empty string yields 0.
- ✗Resetting the run length to 0 instead of 1 on a character change
- ✗Forgetting to compare the final run against the maximum after the loop
- ✗Confusing total character frequency with the longest contiguous run
- →How would you extend this to the longest substring with at most K distinct characters?
- →Why is total frequency not the same as the longest run?
Contents
Task
Find the length of the longest run of identical characters in one O(n) pass.
Solution
int longestRun(const std::string& s) {
if (s.empty()) return 0;
int best = 1, cur = 1;
for (size_t i = 1; i < s.size(); ++i) {
if (s[i] == s[i - 1]) ++cur; // extend the run
else cur = 1; // reset on a change
best = std::max(best, cur);
}
return best;
}Key points
- On a character change the run resets to 1 (the current character already counts), not 0.
- The maximum is updated each step, so no separate flush of the last run is needed.
- This is O(n); the "scan right from each index" variant is O(n²).
Contents
