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 <= 500s consists of only lowercase English letters.The Sliding Window approach iterates through the string keeping track of the current character streak. When the character changes, update the maximum streak length if the current streak is larger. Reset the current streak counter for the new character.
The code initializes two counters: max_power and current_power. As it iterates through the string, if consecutive characters are identical, it increments current_power. If not, it updates max_power if current_power exceeds it, and resets current_power.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) since each character is processed once.
Space Complexity: O(1) as no extra space is used aside from variables.
The recursive approach utilizes memoization to avoid repetitive calculations as it navigates the string, exploring all possibilities for consecutive substrings.
Python's recursive solution uses a cache to store already computed results, progressively calculating the power from the leftmost to the rightmost position of the string. It returns the maximum possible achieved by counting same consecutive characters.
JavaScript
Time Complexity: O(n)
Space Complexity: O(n) due to recursion call stack and cache storage.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) since each character is processed once. |
| Recursive Approach with Memoization | Time Complexity: O(n) |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Consecutive Characters with our built-in code editor and test cases.
Practice on FleetCode