Consecutive Characters
EasyPrompt
The power of the string is the maximum length of a non-empty substring that contains only one unique character.
Given a string s, return the power of s.
Example 1:
Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.Example 2:
Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.
Constraints:
1 <= s.length <= 500sconsists of only lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible substring to see if it consists of only one unique character. We use two nested loops to generate all substrings starting at each possible index.
Algorithm
- Initialize
maxPowerto 1, as the minimum power for a non-empty string is 1. - Iterate through the string with an index
ifrom 0 ton-1to consider each character as a potential start of a sequence. - For each
i, start an inner loop with indexjfromi+1ton-1. - If
s.charAt(j)is the same ass.charAt(i), it means the sequence continues. UpdatemaxPowerwith the maximum of its current value and the length of the current sequence (j - i + 1). - If
s.charAt(j)is different froms.charAt(i), the sequence is broken. Break the inner loop and continue with the next starting characteri+1. - After all iterations, return
maxPower.
Walkthrough
We can iterate through the string with a starting index i. For each i, we start a second loop with index j from i to the end of the string. The inner loop expands a substring starting at i. As long as the character at j is the same as the character at i, we have a valid consecutive character substring. We keep track of the length of this current valid substring (j - i + 1) and update a global maximum length variable. If s.charAt(j) is different from s.charAt(i), the consecutive run is broken for the starting character s.charAt(i), so we can break the inner loop and move to the next starting index i+1. This process is repeated for all possible starting positions.
class Solution { public int maxPower(String s) { if (s == null || s.length() == 0) { return 0; } int maxPower = 1; for (int i = 0; i < s.length(); i++) { for (int j = i + 1; j < s.length(); j++) { if (s.charAt(j) == s.charAt(i)) { maxPower = Math.max(maxPower, j - i + 1); } else { break; } } } return maxPower; }}Complexity
Time
O(n^2), where n is the length of the string `s`. In the worst-case scenario (a string of all identical characters), the inner loop runs approximately `n` times for each of the `n` iterations of the outer loop.
Space
O(1), as we only use a constant amount of extra space for variables like `maxPower`, `i`, and `j`.
Trade-offs
Pros
Conceptually simple and straightforward to write.
Cons
Has a quadratic time complexity, which is inefficient for larger inputs.
A more efficient approach is to iterate through the string just once, keeping track of the length of the current consecutive character sequence.
Algorithm
- Handle the edge case of an empty or null string by returning 0.
- Initialize
maxPower = 1andcurrentPower = 1. - Iterate through the string with an index
ifrom 1 tos.length() - 1. - Compare
s.charAt(i)with the previous characters.charAt(i-1). - If they are the same, increment
currentPower. - If they are different, a sequence has ended. Update
maxPower = Math.max(maxPower, currentPower)and resetcurrentPowerto 1. - After the loop completes, there might be a pending sequence. Perform a final update:
maxPower = Math.max(maxPower, currentPower). - Return
maxPower.
Walkthrough
We can solve this problem in a single pass. We'll maintain two variables: maxPower to store the maximum length found so far, and currentPower to store the length of the current streak of identical characters. We initialize maxPower and currentPower to 1 (for a non-empty string). We then iterate through the string from the second character (i = 1). In each iteration, we compare the current character s.charAt(i) with the previous one s.charAt(i-1). If they are the same, we increment currentPower. If they are different, the streak is broken. We first update maxPower by comparing it with the currentPower of the streak that just ended, and then reset currentPower to 1 for the new character. A crucial step is to perform one final comparison after the loop finishes, as the longest streak might be at the very end of the string.
class Solution { public int maxPower(String s) { if (s == null || s.length() == 0) { return 0; } int maxPower = 1; int currentPower = 1; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { currentPower++; } else { maxPower = Math.max(maxPower, currentPower); currentPower = 1; } } // Final check for the last sequence maxPower = Math.max(maxPower, currentPower); return maxPower; }}Complexity
Time
O(n), where n is the length of the string `s`. We iterate through the string only once.
Space
O(1), as we only use a constant amount of extra space for our counter variables.
Trade-offs
Pros
Optimal time complexity of O(n).
Constant space complexity O(1).
Cons
Requires a final check after the loop to account for a sequence at the end of the string, which can be a minor point of error.
Solutions
Solution
class Solution {public int maxPower(String s) { int ans = 1, t = 1; for (int i = 1; i < s.length(); ++i) { if (s.charAt(i) == s.charAt(i - 1)) { ans = Math.max(ans, ++t); } else { t = 1; } } return ans; }}class Solution {public: int maxPower(string s) { int ans = 1, t = 1; for (int i = 1; i < s.size(); ++i) { if (s[i] == s[i - 1]) { ans = max(ans, ++t); } else { t = 1; } } return ans; }};class Solution: def maxPower(self, s: str) -> int: ans = t = 1 for a, b in pairwise(s): if a == b: t += 1 ans = max(ans, t) else: t = 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.