algoadvance

Leetcode 1446. Consecutive Characters

Problem Statement:

Leetcode 1446 - Consecutive Characters

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

Example:

• Input: s = "abbcccddddeeeeedcba"
• Output: 5
• Explanation: The character ‘e’ is repeated 5 times consecutively.

Clarifying Questions:

1. Can the input string s be empty?
   • For this problem, it is usually safe to assume that the input string will be non-empty unless stated otherwise.
2. What is the expected output if all characters are unique in the string?
   • If all characters are unique, the function should return 1, as the longest sequence of identical characters will be any individual character.
3. What is the length of the input string s?
   • The typical input size for problems like these ranges to thousands or even millions of characters, but we’ll aim for an efficient solution that operates linearly relative to the size of s.

Strategy:

1. Initialize variables to keep track of:
   • maxLength: the longest length of consecutive characters found so far.
   • currentLength: the current length of the ongoing sequence of identical characters.
2. Iterate over the string:
   • Compare each character with the previous one.
   • If they are the same, increment currentLength.
   • If they are different, update maxLength if currentLength is greater, and reset currentLength to 1.
3. After the loop, ensure to update maxLength one final time in case the longest sequence is at the end of the string.

Code:

public int maxPower(String s) {
    // Edge case: if the string is empty.
    if (s == null || s.length() == 0) {
        return 0;
    }

    int maxLength = 1; 
    int currentLength = 1; 

    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) {
            currentLength++;
        } else {
            maxLength = Math.max(maxLength, currentLength);
            currentLength = 1;
        }
    }

    // Final comparison after the loop
    maxLength = Math.max(maxLength, currentLength);

    return maxLength;
}

Time Complexity:

• Time Complexity: O(n), where n is the length of the string s.
  • We make a single linear pass through the string.
• Space Complexity: O(1)
  • The algorithm uses a constant amount of extra space regardless of the input size.

This solution provides an efficient and clear method to determine the length of the longest contiguous substring of the same character in a given string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?