LeetCode 2182: Construct String With Repeat Limit

Problem Description

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

Input: s = “cczazcc”, repeatLimit = 3
Output: “zzcccac”
Explanation: We use all of the characters from s to construct the repeatLimitedString “zzcccac”.
The letter ‘a’ appears at most 1 time in a row.
The letter ‘c’ appears at most 3 times in a row.
The letter ‘z’ appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return “zzcccac”.
Note that the string “zzcccca” is lexicographically larger but the letter ‘c’ appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = “aababab”, repeatLimit = 2
Output: “bbabaa”
Explanation: We use only some of the characters from s to construct the repeatLimitedString “bbabaa”.
The letter ‘a’ appears at most 2 times in a row.
The letter ‘b’ appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return “bbabaa”.
Note that the string “bbabaaa” is lexicographically larger but the letter ‘a’ appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

1 <= repeatLimit <= s.length <= 10⁵
s consists of lowercase English letters.

Difficulty: Medium

Tags: hash table, string, greedy, heap (priority queue), counting

Rating: 93.25%

Solution Approach

The key insight to solving this problem is that we want to:

Use larger letters (later in the alphabet) as much as possible
When we hit the repeat limit, we need to insert a different letter to break up the sequence
After breaking up the sequence, we can return to using the larger letter

Let’s solve this step by step using a max heap (implemented as a min heap with negative ASCII values) and a counter.

The Algorithm

Count the frequency of each character in the input string
Create a max heap of characters (using negative ASCII values for max heap behavior)
Build the result string by:
- Taking the largest available character up to the repeat limit
- If we need to continue with the same character but hit the limit:
  - Insert the next largest available character as a separator
  - Continue with our original character

Detailed Implementation

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        # Count frequency of each character
        count = Counter(s)
        
        # Create max heap using negative ASCII values
        # We store tuples of (-ord(char), char)
        heap = [(-ord(c), c) for c in count]
        heapq.heapify(heap)
        
        result = []
        while heap:
            neg_ascii, char = heappop(heap)
            # Determine how many times we can use the current char
            times = min(repeatLimit, count[char])
            
            # Handle the case where we might exceed repeat limit
            if result and result[-1] == char:
                # If no other chars available, we're done
                if len(heap) == 0:
                    break
                    
                # Get next largest char as separator
                next_neg_ascii, next_char = heappop(heap)
                result.append(next_char)
                count[next_char] -= 1
                
                # If we still have more of the separator char, put it back
                if count[next_char] > 0:
                    heappush(heap, (next_neg_ascii, next_char))
                
                # Put back our original char for next iteration
                heappush(heap, (neg_ascii, char))
                
            else:
                # Add current char up to repeat limit
                result.extend([char] * times)
                count[char] -= times
                # If we still have more of this char, put it back
                if count[char] > 0:
                    heappush(heap, (neg_ascii, char))
        
        return ''.join(result)

Example Walkthrough

Let’s walk through the solution using the example: s = "cczazcc", repeatLimit = 3

Initial state:

Counter: {'c': 4, 'z': 2, 'a': 1}
Heap: [(-ord('z'), 'z'), (-ord('c'), 'c'), (-ord('a'), 'a')]

Step-by-step process:

First iteration:
- Pop ‘z’ (largest char)
- Can use up to min(2, 3) = 2 ‘z’s
- Result: “zz”
- Update counter: {'c': 4, 'z': 0, 'a': 1}
Second iteration:
- Pop ‘c’
- Can use up to 3 ‘c’s
- Result: “zzcccc”
- Update counter: {'c': 1, 'z': 0, 'a': 1}
Third iteration:
- Current result ends in ‘c’
- Need separator, pop ‘a’
- Result: “zzcccac”
- Update counter: {'c': 1, 'z': 0, 'a': 0}

Final result: “zzcccac”

Complexity Analysis

Time Complexity: $O(n)$ , where n is the length of the input string
- Building the counter and heap: O(n)
- Main loop: Each character is processed at most twice (once normally, once as separator)
Space Complexity: $O(1)$
- Counter and heap store at most 26 characters (lowercase English letters)
- Result string is not counted in space complexity per LeetCode conventions