LeetCode 1446 - Consecutive Characters

LeetCode Problem 1446

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to compute the power of a string. The power is defined as the length of the longest contiguous substring that contains only one distinct character.

In simpler terms, we need to find the longest streak of the same character appearing consecutively in the string. We are not looking for the most frequent character overall, only the longest uninterrupted sequence.

For example, in "leetcode", the character 'e' appears consecutively as "ee", which has length 2. No other character forms a longer consecutive sequence, so the answer is 2.

In "abbcccddddeeeeedcba", the substring "eeeee" contains five consecutive 'e' characters. Even though there are also repeated 'd' characters ("dddd"), the sequence of 'e' is longer, so the result is 5.

The input is a single string s consisting only of lowercase English letters. The output is a single integer representing the maximum length of any consecutive block of identical characters.

The constraints are relatively small:

• 1 <= s.length <= 500
• s contains only lowercase English letters

These constraints tell us that performance is not a major concern because the string is short. Even a quadratic solution would pass comfortably. However, the problem has a very natural linear-time solution that scans the string once.

There are several important edge cases to consider. A string of length 1 should return 1, since a single character itself forms a valid substring. A string where every character is the same, such as "aaaaaa", should return the full length of the string. A string with no consecutive repetitions, such as "abcdef", should return 1. The problem guarantees that the string is never empty, so we never need to handle an invalid or empty input.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to examine every possible substring and check whether it contains only one unique character.

For each starting position, we could extend the substring one character at a time and verify whether all characters remain identical. If the substring consists of a single repeated character, we update the maximum length.

This method is correct because it exhaustively considers every candidate substring. Eventually, it will encounter the longest valid substring and record its length.

However, this approach is inefficient. There are O(n²) substrings in total, and validating each substring may take additional work. Even with optimizations, the time complexity becomes unnecessarily large for a problem that only requires tracking consecutive identical characters.

Optimal Approach, Single Pass Tracking

The key observation is that we only care about consecutive runs of characters.

Instead of checking every substring, we can scan the string from left to right and count the length of the current streak of identical characters.

Whenever the current character matches the previous one, we extend the streak. Otherwise, we start a new streak of length 1. While doing this, we continuously track the maximum streak length encountered so far.

This works because every valid substring made of one repeated character belongs to exactly one consecutive run. By measuring each run once, we naturally find the longest one.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks all possible substrings and validates repeated characters
Optimal	O(n)	O(1)	Single scan while counting consecutive identical characters

Algorithm Walkthrough

1. Initialize two variables: current_length and max_length, both starting at 1. Since the string is guaranteed to be non-empty, the smallest valid power is always 1.
2. Iterate through the string starting from index 1, comparing each character with the previous character.
3. If the current character is the same as the previous character, increment current_length because the consecutive streak continues.
4. If the current character differs, reset current_length to 1 because a new streak begins with the current character.
5. After each update, compare current_length with max_length. If the current streak is larger, update max_length.
6. After processing the entire string, return max_length.

Why it works

The algorithm maintains an important invariant: at every position in the string, current_length represents the length of the consecutive sequence ending at the current character, while max_length stores the largest sequence seen so far. Since every consecutive block is processed exactly once, and we update the maximum whenever we find a longer streak, the final value of max_length must be the power of the string.

Python Solution

class Solution:
    def maxPower(self, s: str) -> int:
        current_length = 1
        max_length = 1

        for index in range(1, len(s)):
            if s[index] == s[index - 1]:
                current_length += 1
            else:
                current_length = 1

            max_length = max(max_length, current_length)

        return max_length

The implementation starts by initializing both current_length and max_length to 1, because the string always contains at least one character.

The loop begins from index 1 since each character must be compared with its predecessor. If the current character matches the previous one, the streak continues and current_length increases by one.

When the characters differ, the current streak ends, so we reset current_length to 1, representing the new character starting its own sequence.

After each iteration, we update max_length using max() to ensure we always retain the longest streak encountered during traversal.

Finally, once the scan is complete, we return max_length.

Go Solution

func maxPower(s string) int {
	currentLength := 1
	maxLength := 1

	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			currentLength++
		} else {
			currentLength = 1
		}

		if currentLength > maxLength {
			maxLength = currentLength
		}
	}

	return maxLength
}

The Go implementation follows the exact same logic as the Python solution. Since strings in Go can be indexed directly by byte and the problem guarantees lowercase English letters, character comparison is straightforward.

There are no concerns about integer overflow because the maximum string length is only 500. Since the input is guaranteed to be non-empty, we safely initialize both counters to 1 without special handling for empty strings.

Worked Examples

Example 1

Input: s = "leetcode"

We track the current streak length and the maximum streak found so far.

Index	Character	Previous Character	Current Length	Max Length
0	l	N/A	1	1
1	e	l	1	1
2	e	e	2	2
3	t	e	1	2
4	c	t	1	2
5	o	c	1	2
6	d	o	1	2
7	e	d	1	2

The longest consecutive sequence is "ee", so the answer is 2.

Example 2

Input: s = "abbcccddddeeeeedcba"

Index	Character	Previous Character	Current Length	Max Length
0	a	N/A	1	1
1	b	a	1	1
2	b	b	2	2
3	c	b	1	2
4	c	c	2	2
5	c	c	3	3
6	d	c	1	3
7	d	d	2	3
8	d	d	3	3
9	d	d	4	4
10	e	d	1	4
11	e	e	2	4
12	e	e	3	4
13	e	e	4	4
14	e	e	5	5
15	d	e	1	5
16	c	d	1	5
17	b	c	1	5
18	a	b	1	5

The longest streak is "eeeee" with length 5, so the answer is 5.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the string once, visiting each character exactly one time
Space	O(1)	Only a few integer variables are used

The algorithm is linear because every character is processed exactly once during the traversal. No nested loops or repeated work are involved. Space complexity remains constant because we only maintain counters regardless of input size.

Test Cases

solution = Solution()

assert solution.maxPower("leetcode") == 2  # Example case with repeated 'e'
assert solution.maxPower("abbcccddddeeeeedcba") == 5  # Example case with longest 'eeeee'

assert solution.maxPower("a") == 1  # Minimum input size
assert solution.maxPower("aaaaa") == 5  # Entire string is one repeated character
assert solution.maxPower("abcde") == 1  # No consecutive repetition
assert solution.maxPower("aaabbb") == 3  # Multiple equal maximum streaks
assert solution.maxPower("aabbbbbcc") == 5  # Longest streak in middle
assert solution.maxPower("abcccc") == 4  # Longest streak at end
assert solution.maxPower("zzzza") == 4  # Longest streak at beginning
assert solution.maxPower("abababab") == 1  # Alternating characters
assert solution.maxPower("bbbaaacccddd") == 3  # Several identical maximum streaks

Test	Why
"leetcode"	Verifies the first provided example
"abbcccddddeeeeedcba"	Verifies the second provided example
"a"	Tests minimum valid input
"aaaaa"	Tests when entire string is one sequence
"abcde"	Tests no consecutive duplicates
"aaabbb"	Tests tied maximum streaks
"aabbbbbcc"	Tests longest streak in middle
"abcccc"	Tests longest streak at end
"zzzza"	Tests longest streak at beginning
"abababab"	Tests alternating characters
"bbbaaacccddd"	Tests repeated equal-length streaks

Edge Cases

One important edge case is a string containing only a single character, such as "a". A careless implementation might initialize counters incorrectly or assume there are at least two characters to compare. This implementation handles the case naturally by initializing both counters to 1 and skipping the loop entirely, returning the correct answer.

Another important case is when the entire string consists of one repeated character, such as "aaaaaa". A buggy implementation might forget to update the maximum after extending the streak, especially at the end of the string. Since this solution updates max_length during every iteration, the final longest streak is recorded correctly.

A third edge case occurs when there are no repeated adjacent characters, such as "abcdef". In this situation, every streak has length 1. The implementation correctly resets current_length to 1 at every character transition, and max_length never exceeds 1.

A final tricky case is when multiple streaks have the same maximum length, such as "aaabbbccc". The algorithm does not need to track which character created the streak, only the maximum length. Because max_length stores the best result seen so far, ties are handled automatically and the correct value is returned.