Skip to main content
Talentd

Maximum Number of Equal Length Runs - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringCounting6 min read
Practice this problem

Problem Statement

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 <= 105
  • s consists of lowercase English letters only.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Run ComparisonO(n^2)O(n)Useful for understanding the structure of runs and validating logic on small inputs
Hash Table CountingO(n)O(n)General case. Efficient single-pass solution expected in interviews

Frequently Asked Questions

Is Maximum Number of Equal Length Runs easy or hard?
The problem is typically rated Medium because it requires recognizing runs in a string and converting the task into a frequency counting problem. The implementation itself is simple, but identifying the single-pass counting approach is the key insight.
Maximum Number of Equal Length Runs Python/Java solution
Most implementations iterate through the string while maintaining a counter for the current run. When a run ends, its length is recorded in a hash map and the counter resets. This logic is straightforward to implement in Python dictionaries, Java HashMap, C++ unordered_map, Go maps, or TypeScript objects.
How to solve Maximum Number of Equal Length Runs in O(n)?
Traverse the string and count the length of each contiguous block of identical characters. When the character changes, insert the completed run length into a hash map and increment its frequency. Maintain a variable storing the highest frequency seen so far. The final maximum frequency represents the largest number of runs with equal length.
What is the best approach for Maximum Number of Equal Length Runs?
The most efficient approach uses a hash table to count how many runs occur for each run length. Scan the string once, compute each run length, and store its frequency in a map. Track the maximum frequency while updating the map. This achieves O(n) time and O(n) space complexity.
Is Maximum Number of Equal Length Runs asked at Google/Amazon/Meta?
String run detection and frequency counting problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often involve grouping consecutive characters, run-length encoding, or counting segment properties. This problem tests similar reasoning and hash map usage.
What data structure is used in Maximum Number of Equal Length Runs?
The primary data structure is a hash table (or dictionary) that maps run lengths to their frequency. The algorithm also uses simple variables to track the current run length while scanning the string. This combination allows efficient counting in a single pass.
What is the time complexity of Maximum Number of Equal Length Runs?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once while detecting run boundaries. Hash table updates and lookups occur in constant average time, keeping the overall complexity linear.

Ready to solve this problem?

Practice Maximum Number of Equal Length Runs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters