Problem Description

You are given a string s. The power of a string is defined as the maximum length of a non-empty substring that contains only one unique character (all characters in the substring are the same).

Your task is to find and return the power of the given string s.

For example:

• If s = "leetcode", the power is 2 because "ee" is the longest substring with only one unique character
• If s = "abbcccddddeeeeedcba", the power is 5 because "eeeee" is the longest substring with only one unique character
• If s = "triplepillooooow", the power is 5 because "ooooo" is the longest substring with only one unique character

The solution works by traversing through the string and keeping track of consecutive identical characters. It uses a variable t to count the current streak of identical characters. When it encounters a different character, it resets the counter to 1. Throughout the traversal, it maintains the maximum streak found, which represents the power of the string.

Intuition

To find the longest substring with only one unique character, we need to identify consecutive sequences of the same character. The key insight is that we can solve this problem in a single pass through the string by tracking consecutive identical characters.

Think of it like counting steps while walking - every time you take a step in the same direction, you increment your counter. When you change direction, you reset your counter to 1 and start counting again. Throughout your walk, you keep track of the maximum number of consecutive steps in any single direction.

Similarly, as we traverse the string character by character, we can compare each character with its previous one. If they match, we're extending our current sequence of identical characters, so we increment our counter t. If they don't match, we've encountered a new character, which starts a new sequence, so we reset t = 1.

The beauty of this approach is its simplicity - we don't need to generate all possible substrings or use complex data structures. By using the pairwise function to look at adjacent character pairs (a, b), we can elegantly check if consecutive characters are the same. We maintain the maximum length seen so far in ans, updating it whenever we find a longer sequence.

This greedy approach works because the power of a string depends only on finding the maximum length, not on tracking all sequences. We can determine the answer in O(n) time with just a single traversal.

Solution Approach

The implementation uses a traversal and counting technique to find the maximum length of consecutive identical characters.

We initialize two variables:

• ans = 1: Stores the maximum power found so far (initialized to 1 since any single character has power 1)
• t = 1: Tracks the current length of consecutive identical characters

The algorithm leverages Python's pairwise function to iterate through adjacent character pairs in the string. For each pair (a, b):

1. If characters match (a == b):

   • Increment the current streak: t += 1
   • Update the maximum if needed: ans = max(ans, t)
   • This means we're extending our current sequence of identical characters

2. If characters don't match (a != b):

   • Reset the counter: t = 1
   • This indicates we've encountered a different character and must start counting a new sequence

The pairwise function creates sliding windows of size 2, giving us pairs like:

• For string "aabbb", we get pairs: ('a','a'), ('a','b'), ('b','b'), ('b','b')

This approach ensures we examine every transition point in the string where characters might change or continue. By maintaining the running maximum in ans, we capture the longest sequence without needing to store all sequences.

The time complexity is O(n) where n is the length of the string, as we traverse the string once. The space complexity is O(1) as we only use a constant amount of extra space for our variables.

Example Walkthrough

Let's walk through the solution with the string s = "abbcccddddeeeeedcba".

We initialize:

• ans = 1 (maximum power found so far)
• t = 1 (current streak of identical characters)

Now we traverse through adjacent character pairs:

1. Pair ('a', 'b'): Different characters

   • t = 1 (reset counter)
   • ans = 1

2. Pair ('b', 'b'): Same characters

   • t = 2 (increment streak)
   • ans = max(1, 2) = 2

3. Pair ('b', 'c'): Different characters

   • t = 1 (reset counter)
   • ans = 2

4. Pair ('c', 'c'): Same characters

   • t = 2
   • ans = max(2, 2) = 2

5. Pair ('c', 'c'): Same characters

   • t = 3
   • ans = max(2, 3) = 3

6. Pair ('c', 'd'): Different characters

   • t = 1
   • ans = 3

7. Pairs ('d', 'd'), ('d', 'd'), ('d', 'd'): All same characters

   • t increases: 2 → 3 → 4
   • ans = max(3, 4) = 4

8. Pair ('d', 'e'): Different characters

   • t = 1
   • ans = 4

9. Pairs ('e', 'e'), ('e', 'e'), ('e', 'e'), ('e', 'e'): All same characters

   • t increases: 2 → 3 → 4 → 5
   • ans = max(4, 5) = 5

10. Remaining pairs lead to different characters or shorter streaks

Final answer: 5 (from the substring "eeeee")

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the pairwise function iterates through the string once, creating pairs of consecutive characters. Each pair is processed exactly once in the for loop, performing constant-time operations (comparison, increment, and max calculation) for each pair. Since there are n-1 pairs for a string of length n, the overall time complexity is linear.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. The variables ans and t are simple integers that don't scale with the input. The pairwise function generates pairs on-the-fly without storing all pairs in memory, using an iterator that maintains only a constant amount of state. Therefore, the space usage remains constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Single Character Strings

A common mistake is not properly initializing the variables or not handling edge cases where the string has only one character.

Pitfall Example:

def maxPower(self, s: str) -> int:
    max_length = 0  # Wrong initialization!
    current_streak = 0  # Wrong initialization!
  
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            current_streak += 1
            max_length = max(max_length, current_streak)
        else:
            current_streak = 1
  
    return max_length  # Returns 0 for single character strings!

Solution: Always initialize both max_length and current_streak to 1, since any non-empty string has at least a power of 1.

2. Not Updating Maximum for the Last Streak

When the longest consecutive sequence occurs at the end of the string, failing to update the maximum after the loop can lead to incorrect results.

Pitfall Example:

def maxPower(self, s: str) -> int:
    max_length = 1
    current_streak = 1
  
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            current_streak += 1
            # Only updating here might miss the final streak
        else:
            max_length = max(max_length, current_streak)
            current_streak = 1
  
    return max_length  # Misses updating for string ending with longest streak!

Solution: Either update max_length inside the matching condition (as shown in the correct solution) or add a final check after the loop: return max(max_length, current_streak).

3. Off-by-One Errors in Loop Range

Using incorrect loop boundaries can cause index out of bounds errors or miss character comparisons.

Pitfall Example:

def maxPower(self, s: str) -> int:
    max_length = 1
    current_streak = 1
  
    for i in range(len(s)):  # Goes up to len(s) - 1
        if s[i] == s[i + 1]:  # IndexError when i = len(s) - 1!
            current_streak += 1
            max_length = max(max_length, current_streak)
        else:
            current_streak = 1
  
    return max_length

Solution: Always use range(len(s) - 1) when comparing consecutive elements to avoid accessing index out of bounds.

4. Resetting Counter to 0 Instead of 1

When encountering a different character, resetting the counter to 0 instead of 1 leads to incorrect counting.

Pitfall Example:

def maxPower(self, s: str) -> int:
    max_length = 1
    current_streak = 1
  
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            current_streak += 1
            max_length = max(max_length, current_streak)
        else:
            current_streak = 0  # Wrong! Should be 1
  
    return max_length

Solution: Always reset current_streak to 1 when characters differ, as the new character itself forms a streak of length 1.