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.Problem Overview: You are given a string and need to determine how many contiguous runs of identical characters share the same length. A run is a maximal substring of the same character (for example, "aaa" or "bb"). The goal is to compute the maximum number of runs that have identical lengths.
Approach 1: Brute Force Run Comparison (O(n^2) time, O(n) space)
Start by scanning the string and extracting every run of identical characters along with its length. Store the run lengths in an array. Then compare every run length with every other run length and count how many times each length appears. The maximum frequency among these counts is the answer. This works but performs unnecessary repeated comparisons because the same run lengths get counted multiple times. The nested iteration leads to O(n^2) time in the worst case, while storing run lengths requires O(n) space.
Approach 2: Hash Table Counting (O(n) time, O(n) space)
Process the string once and compute the length of each run. Maintain a counter for the current run while iterating character by character. Whenever the character changes, record the completed run length in a hash table where the key is the run length and the value is how many runs of that length have appeared so far. Update the maximum frequency during insertion. This removes redundant comparisons because each run length is counted exactly once using constant-time hash lookups.
The key insight: you only care about the frequency of each run length, not the runs themselves. A hash table maps each length to its count efficiently. The string is scanned once, making the algorithm linear. Run detection uses simple character comparisons, which is typical in many string traversal problems. This pattern—scan, aggregate counts, and track a maximum—is common in counting problems.
Recommended for interviews: The hash table counting approach is what interviewers expect. It shows you can recognize runs during a single pass and convert the problem into a frequency counting task. Mentioning the brute force comparison first demonstrates understanding of the problem structure, but the optimal solution demonstrates practical algorithmic thinking with O(n) time complexity.
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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Run Comparison | O(n^2) | O(n) | Useful for understanding the structure of runs and validating logic on small inputs |
| Hash Table Counting | O(n) | O(n) | General case. Efficient single-pass solution expected in interviews |
Practice Maximum Number of Equal Length Runs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor