Problem

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

Example 1:

1
2
3

Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.

Example 2:

1
2
3

Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.

Solution

Method 1 - Using counter

To solve this problem, we iterate through the string and keep track of the length of the current sequence of identical characters. We also maintain a variable for the maximum length found.

  1. Initialize Variables:
    • maxPower to record the maximum length of a substring of identical characters.
    • currentPower to record the length of the current sequence of identical characters.
    • previousChar to keep track of the character in the current sequence.
  2. Iterate Through Characters:
    • For each character in the string, if it matches previousChar, increment currentPower.
    • If it does not match, update maxPower if currentPower is larger, then reset currentPower to 1 and update previousChar.
  3. Final Update:
    • After iterating through the string, ensure to update maxPower with currentPower one last time to handle the end of the string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public int maxPower(String s) {
        int maxPower = 1, currentPower = 1;
        char previousChar = s.charAt(0);

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == previousChar) {
                currentPower++;
            } else {
                maxPower = Math.max(maxPower, currentPower);
                currentPower = 1;
                previousChar = s.charAt(i);
            }
        }

        maxPower = Math.max(maxPower, currentPower);
        return maxPower;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string s, as we process each character once.
  • 🧺 Space complexity: O(1) since we use a constant amount of extra space for variables.