Consecutive Characters

Difficulty: Easy | Acceptance: 60.40% | Paid: No Topics: String

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.

• Examples
• Constraints
• Brute Force
• Single Pass

Examples

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 <= 500
s consists of only lowercase English letters.

Brute Force

Intuition Check every possible substring to see if it consists of only one unique character and keep track of the maximum length found.

Steps

• Iterate through the string with a pointer i representing the start of the substring.
• Iterate with a pointer j from i to the end of the string.
• For each substring s[i...j], check if all characters are the same.
• If they are, update the maximum power.

class Solution:
    def maxPower(self, s: str) -> int:
        n = len(s)
        max_len = 0
        for i in range(n):
            for j in range(i, n):
                if len(set(s[i:j+1])) == 1:
                    max_len = max(max_len, j - i + 1)
        return max_len

Complexity

• Time: O(n³) or O(n²) depending on implementation details (checking substring validity takes O(k) where k is length). In the worst case, this is O(n²) if we check efficiently, but the provided solution is roughly O(n³) due to substring creation/iteration inside loops.
• Space: O(1) or O(k) for substring extraction depending on language.
• Notes: Simple to implement but inefficient for large strings.

Single Pass

Intuition Traverse the string once, maintaining a running count of the current consecutive character sequence. Update the maximum whenever the sequence breaks or ends.

Steps

• Initialize max_power and current_count to 1.
• Iterate from the second character to the end.
• If the current character is the same as the previous one, increment current_count.
• Otherwise, reset current_count to 1.
• Update max_power with the maximum of itself and current_count.

class Solution:
    def maxPower(self, s: str) -> int:
        if not s:
            return 0
        max_len = 1
        curr_len = 1
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                curr_len += 1
            else:
                max_len = max(max_len, curr_len)
                curr_len = 1
        return max(max_len, curr_len)

Complexity

• Time: O(n) - We traverse the string exactly once.
• Space: O(1) - We only use a few variables for counting.
• Notes: This is the optimal solution for this problem.