Consecutive Characters — Solution in Python, Java & C++
Consecutive Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Consecutive Characters is an easy coding problem on strings and two pointers, asked in Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Strings, Two Pointers
- Asked at: Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The power of a string is the length of its longest non-empty substring made of a single repeated character.
Given a lowercase string s, return its power.
Example 1
Input: s = "keeeeeep"
Output: 6
Explanation: The substring `"eeeeee"` has length 6.
Example 2
Input: s = "codekairo"
Output: 1
Example 3
Input: s = "aabbbbcc"
Output: 4
Constraints
1 <= s.length <= 500s consists of only lowercase English letters
Hints for Consecutive Characters
Hint 1
Only runs of equal adjacent characters matter.
Hint 2
Scan once, tracking the length of the current run.
Hint 3
Extend the run when a character equals the previous one, otherwise restart it at 1; keep the maximum.
How to solve Consecutive Characters
The answer is the longest run of equal adjacent characters, which a single pass with a running counter finds.
Approach
- Set
best = run = 1. - For
ifrom 1: ifs[i] == s[i-1], incrementrun, otherwise resetrun = 1. - After each step set
best = max(best, run). - Return
best.
Why it works
Any single-character substring lies inside one maximal run, so its length is at most that run's length; the counter measures each maximal run in full before it is reset, so the maximum over runs is found.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Start
bestat 1, not 0 — a one-character string has power 1. - Update the maximum while the run grows, or the final run at the end of the string is missed.
Reference solution
Python
def maxPower(s: str) -> int:
best = run = 1
for i in range(1, len(s)):
run = run + 1 if s[i] == s[i - 1] else 1
best = max(best, run)
return bestJava
public static int maxPower(String s) {
int best = 1, run = 1;
for (int i = 1; i < s.length(); i++) {
run = s.charAt(i) == s.charAt(i - 1) ? run + 1 : 1;
best = Math.max(best, run);
}
return best;
}C++
int maxPower(string s) {
int best = 1, run = 1;
for (int i = 1; i < (int)s.size(); i++) {
run = s[i] == s[i - 1] ? run + 1 : 1;
best = max(best, run);
}
return best;
}JavaScript
var maxPower = function(s) {
var best = 1, run = 1;
for (var i = 1; i < s.length; i++) {
run = s[i] === s[i - 1] ? run + 1 : 1;
if (run > best) best = run;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique