algoadvance

Given a string s, the task is to find the length of the longest contiguous substring of the same character.

Example:

Constraints:

Clarifying Questions

  1. Is the string guaranteed to contain only lowercase English letters?
    • Yes, as per constraints.
  2. Is the input string allowed to be empty?
    • No, the minimum length is 1.

No further clarifications needed. Let’s proceed to the solution strategy.

Strategy

To find the length of the longest contiguous substring of the same character, we can maintain a counter that tracks the length of the current contiguous substring and another counter for the maximum length found so far:

  1. Initialize max_length to 1 (since the minimum length is 1).
  2. Initialize current_length to 1 for the first character.
  3. Iterate over the string starting from the second character:
    • If the current character is the same as the previous one, increment current_length.
    • If it is different, compare current_length with max_length and update max_length if necessary, then reset current_length to 1.
  4. After the loop ends, compare current_length one last time with max_length.
  5. Return max_length.

Code

def maxPower(s: str) -> int:
    if not s:
        return 0

    max_length = 1
    current_length = 1

    for i in range(1, s.length):
        if s[i] == s[i - 1]:
            current_length += 1
        else:
            max_length = max(max_length, current_length)
            current_length = 1

    max_length = max(max_length, current_length)
    return max_length

# Example usage
s = "abbcccddddeeeeedcba"
print(maxPower(s))  # Output is 5

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string s. We iterate through the string once, making the solution efficient. The space complexity is O(1) as we use a constant amount of extra space.

Try our interview co-pilot at AlgoAdvance.com