You are given a string s consisting of lowercase English letters.
A run in s is a substring of equal letters that cannot be extended further. For example, the runs in "hello" are "h", "e", "ll", and "o".
You can select runs that have the same length in s.
Return an integer denoting the maximum number of runs you can select in s.
Example 1:
Input: s = "hello"
Output: 3
Explanation:
The runs in s are "h", "e", "ll", and "o". You can select "h", "e", and "o" because they have the same length 1.
Example 2:
Input: s = "aaabaaa"
Output: 2
Explanation:
The runs in s are "aaa", "b", and "aaa". You can select "aaa" and "aaa" because they have the same length 3.
Constraints:
1 <= s.length <= 105s consists of lowercase English letters only.We can use a hash table cnt to record the number of occurrences of each run length. We traverse the string s, and for each run, we calculate its length m and increment cnt[m] by 1. Finally, the answer is the maximum value in cnt.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Java
C++
Go
TypeScript
Practice Maximum Number of Equal Length Runs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor