JuniorCodeCommonNot answered yet
Per-character maximum consecutive repetition count
For each distinct character in a string, report the maximum number of times it appears consecutively anywhere in the string. For "aaBaaaaBffc" the answer for a is 4, for B is 1, for f is 2, for c is 1.
Requirements:
- O(n) time, one pass; comparison is case-sensitive.
std::map<char,int> maxRepeats(const std::string& s) {
// your code here
}Write the implementation.
Walk the string tracking the current character and its run length. When the character changes, update that character's recorded maximum in a map if the just-ended run is longer, then start a new run of length 1. Flush the last run after the loop. One pass, O(n) time.
- ✗Reporting total frequency instead of the longest consecutive run
- ✗Forgetting to flush the final run after the loop ends
- ✗Folding case when the spec is case-sensitive (or vice versa)
- →Why does sorting destroy the answer for an interleaved character like
aba? - →How would you keep the output keys in first-appearance order instead of sorted?
Contents
Task
For each character report its longest consecutive run, in one O(n) pass.
Solution
std::map<char,int> maxRepeats(const std::string& s) {
std::map<char,int> best;
if (s.empty()) return best;
char prev = s[0]; int run = 1;
auto flush = [&](char c, int r) { best[c] = std::max(best[c], r); };
for (size_t i = 1; i < s.size(); ++i) {
if (s[i] == prev) ++run;
else { flush(prev, run); prev = s[i]; run = 1; }
}
flush(prev, run); // the last run
return best;
}Key points
- The consecutive run is tracked, not the total frequency (matters for
aba). - The final run is flushed after the loop separately.
- Comparison is case-sensitive; one O(n) pass.
Contents
