LeetCode 3773 - Maximum Number of Equal Length Runs

The problem asks us to analyze a string s consisting of lowercase English letters and identify runs, which are contiguous sequences of identical characters that cannot be extended further. For example, in "aaabaaa", the runs are "aaa", "b", and "aaa".

leetcodemediumhash-tablestringcounting

LeetCode Problem 3773

Difficulty: 🟡 Medium
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem asks us to analyze a string s consisting of lowercase English letters and identify runs, which are contiguous sequences of identical characters that cannot be extended further. For example, in "aaabaaa", the runs are "aaa", "b", and "aaa". The goal is to select runs that all have the same length and maximize the number of runs chosen. The output should be the count of these runs.

The input is a string of length up to 10^5, so any solution must be linear or near-linear to perform efficiently. The output is a single integer representing the maximum number of runs of equal length that can be chosen.

Important points and edge cases include strings with all identical characters (e.g., "aaaaa"), strings with alternating characters (e.g., "ababab"), and single-character strings (e.g., "a"). These cases test if the implementation correctly handles runs of varying lengths and extremes.

Approaches

The brute-force approach would be to identify all possible runs, then for each unique length, count how many runs exist, and finally select the length with the maximum count. While correct, it requires multiple passes over the string and storage of all run substrings, which can be inefficient for large strings.

The optimal approach leverages the insight that we do not need the run substrings themselves, only their lengths. We can traverse the string once, record the length of each run, and maintain a frequency count of run lengths in a hash map. The answer is simply the maximum frequency of any run length. This approach is linear in time and space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Extract all runs as substrings, then count occurrences of each length. Too slow for n = 10^5.
Optimal O(n) O(n) Traverse string once, count run lengths using a hash map, return max frequency.

Algorithm Walkthrough

  1. Initialize a hash map length_count to store frequencies of run lengths and a pointer i = 0 to traverse the string.
  2. While i < len(s), start a run with length 1.
  3. Increment a temporary pointer j while s[j] == s[i] to find the extent of the current run.
  4. Calculate the run length as j - i and increment the frequency for this length in length_count.
  5. Move i to j to start processing the next run.
  6. After traversing the entire string, the hash map contains counts of all run lengths. Return the maximum frequency among these values.

Why it works: Each run is counted exactly once, and the hash map guarantees we correctly track how many runs exist for each length. By taking the maximum frequency, we select the run length that allows the largest number of runs to be chosen, satisfying the problem requirement.

Python Solution

class Solution:
    def maxSameLengthRuns(self, s: str) -> int:
        from collections import defaultdict
        
        length_count = defaultdict(int)
        n = len(s)
        i = 0
        
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            run_length = j - i
            length_count[run_length] += 1
            i = j
        
        return max(length_count.values())

The Python code uses a defaultdict to count run lengths efficiently. The outer loop iterates through the string, and the inner loop extends the current run. By storing only run lengths, we avoid unnecessary memory usage, and max(length_count.values()) efficiently returns the answer.

Go Solution

func maxSameLengthRuns(s string) int {
    lengthCount := make(map[int]int)
    n := len(s)
    i := 0
    
    for i < n {
        j := i + 1
        for j < n && s[j] == s[i] {
            j++
        }
        runLength := j - i
        lengthCount[runLength]++
        i = j
    }
    
    maxCount := 0
    for _, count := range lengthCount {
        if count > maxCount {
            maxCount = count
        }
    }
    
    return maxCount
}

In Go, we use a map to count run lengths. The loops mirror the Python solution, and a final iteration over the map finds the maximum frequency. Go handles empty slices and maps naturally, so no special nil checks are needed here.

Worked Examples

Example 1: s = "hello"

Run Start-End Length Count
"h" 0-0 1 1
"e" 1-1 1 2
"ll" 2-3 2 1
"o" 4-4 1 3

Maximum frequency = 3 → Answer: 3

Example 2: s = "aaabaaa"

Run Start-End Length Count
"aaa" 0-2 3 1
"b" 3-3 1 1
"aaa" 4-6 3 2

Maximum frequency = 2 → Answer: 2

Complexity Analysis

Measure Complexity Explanation
Time O(n) We traverse the string once and extend each run once. Inner loop increments pointer without revisiting characters.
Space O(n) Hash map may store up to n distinct run lengths in worst case (alternating characters).

The time complexity is optimal for the input constraint n <= 10^5.

Test Cases

# Provided examples
assert Solution().maxSameLengthRuns("hello") == 3  # max runs of length 1
assert Solution().maxSameLengthRuns("aaabaaa") == 2  # max runs of length 3

# Single character
assert Solution().maxSameLengthRuns("a") == 1

# All identical
assert Solution().maxSameLengthRuns("aaaaa") == 1  # only one run of length 5

# Alternating characters
assert Solution().maxSameLengthRuns("ababab") == 3  # six runs of length 1

# Multiple run lengths with tie
assert Solution().maxSameLengthRuns("aaabbcc") == 2  # "aa" and "bb" or "bb" and "cc"

# Maximum length string (stress test)
assert Solution().maxSameLengthRuns("a"*100000) == 1
Test Why
"hello" Basic test with runs of length 1 and 2
"aaabaaa" Runs of length 1 and 3, max count is length 3
"a" Minimum input size
"aaaaa" Single run occupying whole string
"ababab" Alternating characters, all runs length 1
"aaabbcc" Tie between different run lengths
"a"*100000 Stress test for large input

Edge Cases

All identical characters: For "aaaaa", there is only one run. The implementation correctly counts the single run and returns 1. No inner loop boundary errors occur because we increment the index past the last character.

Alternating characters: In "ababab", runs are all length 1. The algorithm correctly identifies multiple runs of the same length and returns their count.

Single-character string: For "a", the run length is 1, and the algorithm correctly handles the string without accessing out-of-bounds indices.

Tie between run lengths: For strings like "aaabbcc", the algorithm returns the maximum frequency among lengths, ensuring it picks the optimal number of runs without bias toward larger or smaller run lengths.

This approach handles all edge cases efficiently and correctly, with linear time complexity and minimal space overhead.