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.

Description Hints 2 Solution

3773. Maximum Number of Equal Length Runs

Medium82.8% acceptancePremium elsewhere, free here

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

Topics

Hints open one at a time

Hint 1

Split the string when adjacent characters are not equal, and use those to make the runs

Hint 2

Use a hashmap to group runs of the same length

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"hello"

Input

"aaabaaa"

Your code is saved on this device.Solution