{x}
blog image

Consecutive Characters

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

Solution Explanation for Consecutive Characters

The problem asks to find the maximum length of a substring containing only one unique character. This is essentially finding the longest consecutive sequence of identical characters within a given string.

Approach: Single Pass Traversal

The most efficient approach is a single-pass traversal of the string. We maintain two variables:

  • max_power: Stores the maximum length of a consecutive substring encountered so far. Initialized to 1 (a single character is a valid substring).
  • current_power: Stores the length of the current consecutive substring being processed. Initialized to 1.

The algorithm iterates through the string, comparing each character with the previous one.

  • If the characters are the same: We increment current_power and update max_power if current_power is greater.
  • If the characters are different: We reset current_power to 1, as a new consecutive sequence starts.

After iterating through the entire string, max_power holds the maximum length of the consecutive substring.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string only once.
  • Space Complexity: O(1). We use only a few constant extra variables.

Code Implementation in Multiple Languages

Python

def maxPower(s: str) -> int:
    max_power = 1
    current_power = 1
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            current_power += 1
        else:
            max_power = max(max_power, current_power)
            current_power = 1
    max_power = max(max_power, current_power) #Handle the last sequence.
    return max_power

Java

class Solution {
    public int maxPower(String s) {
        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;
            }
        }
        maxPower = Math.max(maxPower, currentPower); //Handle last sequence
        return maxPower;
    }
}

C++

class Solution {
public:
    int maxPower(string s) {
        int max_power = 1;
        int current_power = 1;
        for (size_t i = 1; i < s.length(); ++i) {
            if (s[i] == s[i - 1]) {
                current_power++;
            } else {
                max_power = max(max_power, current_power);
                current_power = 1;
            }
        }
        max_power = max(max_power, current_power); //Handle last sequence
        return max_power;
    }
};

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var maxPower = function(s) {
    let maxPower = 1;
    let currentPower = 1;
    for (let i = 1; i < s.length; i++) {
        if (s[i] === s[i - 1]) {
            currentPower++;
        } else {
            maxPower = Math.max(maxPower, currentPower);
            currentPower = 1;
        }
    }
    maxPower = Math.max(maxPower, currentPower); //Handle last sequence
    return maxPower;
};

These code snippets all follow the same algorithmic approach, differing only in syntax. They all achieve a time complexity of O(n) and space complexity of O(1). The handling of the last sequence (ensuring the last consecutive substring is considered) is crucial for correctness.