Consecutive Characters

EASY

Description

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.

Approaches

Checkout 2 different approaches to solve Consecutive Characters. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

This approach involves checking every possible substring to see if it consists of only one unique character. We use two nested loops to generate all substrings starting at each possible index.

Algorithm

Initialize maxPower to 1, as the minimum power for a non-empty string is 1.
Iterate through the string with an index i from 0 to n-1 to consider each character as a potential start of a sequence.
For each i, start an inner loop with index j from i+1 to n-1.
If s.charAt(j) is the same as s.charAt(i), it means the sequence continues. Update maxPower with the maximum of its current value and the length of the current sequence (j - i + 1).
If s.charAt(j) is different from s.charAt(i), the sequence is broken. Break the inner loop and continue with the next starting character i+1.
After all iterations, return maxPower.

We can iterate through the string with a starting index i. For each i, we start a second loop with index j from i to the end of the string. The inner loop expands a substring starting at i. As long as the character at j is the same as the character at i, we have a valid consecutive character substring. We keep track of the length of this current valid substring (j - i + 1) and update a global maximum length variable. If s.charAt(j) is different from s.charAt(i), the consecutive run is broken for the starting character s.charAt(i), so we can break the inner loop and move to the next starting index i+1. This process is repeated for all possible starting positions.

class Solution {
    public int maxPower(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int maxPower = 1;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (s.charAt(j) == s.charAt(i)) {
                    maxPower = Math.max(maxPower, j - i + 1);
                } else {
                    break;
                }
            }
        }
        return maxPower;
    }
}

Complexity Analysis

Time Complexity: O(n^2), where n is the length of the string `s`. In the worst-case scenario (a string of all identical characters), the inner loop runs approximately `n` times for each of the `n` iterations of the outer loop.Space Complexity: O(1), as we only use a constant amount of extra space for variables like `maxPower`, `i`, and `j`.

Pros and Cons

Pros:

Conceptually simple and straightforward to write.

Cons:

Has a quadratic time complexity, which is inefficient for larger inputs.

Code Solutions

Checking out 3 solutions in different languages for Consecutive Characters. Click on different languages to view the code.

class Solution {
public
  int maxPower(String s) {
    int ans = 1, t = 1;
    for (int i = 1; i < s.length(); ++i) {
      if (s.charAt(i) == s.charAt(i - 1)) {
        ans = Math.max(ans, ++t);
      } else {
        t = 1;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Consecutive Characters

Data Structures:

String