1446. Consecutive Characters
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 61.4%
Problem Breakdown
The problem asks us to find the maximum length of a substring within a given string s that contains only one unique character. The input is a single string s consisting of lowercase English letters, and the output should be an integer representing the power of the string.
Inputs:
- A string
s(1 <= s.length <= 500)
Outputs:
- An integer representing the maximum length of a substring with only one unique character
Implicit Constraints/Edge Cases:
- The string can contain only lowercase English letters.
- If the string is empty, the power should be 0 (though the problem constraints state that the string will not be empty).
- The string could have all characters the same, or it could have no consecutive repeating characters.
Intuition
A brute-force approach would involve checking every possible substring of s to see if it contains only one unique character. This would result in a time complexity of O(n^3) due to generating substrings and checking their uniqueness, which is inefficient for the given constraints.
The key insight is to use a single pass through the string while keeping track of consecutive characters. By maintaining a count of consecutive identical characters as we iterate through the string, we can efficiently determine the maximum length of such substrings without needing to generate or check every possible substring.
Approach
- Initialize two variables:
max_powerto keep track of the maximum length found andcurrent_powerto count the current sequence of identical characters. - Iterate through the string starting from the second character:
- If the current character is the same as the previous one, increment
current_power. - Otherwise, update
max_powerifcurrent_poweris greater thanmax_power, and resetcurrent_powerto 1 (since we are starting a new sequence).
- If the current character is the same as the previous one, increment
- After the loop, perform a final check to update
max_powerin case the longest sequence ends at the last character of the string. - Return
max_power.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We make a single pass through the string.
- Space Complexity: O(1). We use only a constant amount of extra space for variables.
Solution
def maxPower(s: str) -> int:
if not s:
return 0
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
# Final check to update max_power
max_power = max(max_power, current_power)
return max_power
Edge Cases Handled
- Single character string: The loop will not execute, and
max_powerwill be set to 1. - All characters the same: The loop will increment
current_powerfor each character, andmax_powerwill be updated accordingly. - No consecutive repeating characters: Each character will reset
current_powerto 1, andmax_powerwill remain 1.