algoadvance

Leetcode 1446. Consecutive Characters

Problem Statement

Given a string s, the task is to find the length of the longest substring containing only one unique character.

Clarifying Questions

  1. Input Constraints:
    • Is the string s composed only of lowercase/uppercase English letters?
    • Can the string be empty?
  2. Output Constraints:
    • Should the function return 0 for an empty string?
    • Are there any specific edge cases we should consider, such as strings with all similar characters?

Strategy

The problem requires finding the length of the longest contiguous substring that contains the same character. Here’s a step-by-step strategy to solve this problem:

  1. Initialize Variables:
    • Use a variable maxLength to keep track of the maximum length found.
    • Use a variable currentChar to track the current character being considered.
    • Use a variable currentLength to track the length of the current sequence of identical characters.
  2. Iterate Through the String:
    • Traverse the string character by character.
    • If the current character is the same as the currentChar, increase the currentLength.
    • If the current character is different, update maxLength if currentLength is greater, and then reset currentChar and currentLength.
  3. Final Check:
    • After the loop, there might be a case where the longest sequence is at the end of the string, so perform a final update to maxLength.

Code

Here’s how you can implement the above strategy in C++:

#include <string>
#include <algorithm>

class Solution {
public:
    int maxPower(std::string s) {
        if (s.empty()) return 0;
        
        int maxLength = 1;  // At least one character long sequence exists
        int currentLength = 1;
        char currentChar = s[0];
        
        for (int i = 1; i < s.length(); ++i) {
            if (s[i] == currentChar) {
                currentLength++;
            } else {
                maxLength = std::max(maxLength, currentLength);
                currentChar = s[i];
                currentLength = 1;
            }
        }
        
        // Final comparison to catch sequences at the end of the string
        maxLength = std::max(maxLength, currentLength);
        
        return maxLength;
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string s. This is because we only need to pass through the string once, performing constant-time operations at each step.

The space complexity is O(1) since we are using only a fixed amount of extra space regardless of the input size.

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