Problem Description

You are given a string s and an integer repeatLimit. Your task is to construct a new string called repeatLimitedString using the characters from s, with the constraint that no letter can appear more than repeatLimit times consecutively. You don't need to use all the characters from s.

The goal is to return the lexicographically largest possible repeatLimitedString.

What makes a string lexicographically larger?

• A string a is lexicographically larger than string b if at the first position where they differ, string a has a letter that comes later in the alphabet than the corresponding letter in b.
• If the first min(a.length, b.length) characters are identical, then the longer string is considered lexicographically larger.

Example understanding:

• If s = "cczazcc" and repeatLimit = 3, you need to rearrange the characters to create the largest possible string where no character repeats more than 3 times in a row.
• Characters available: c(4), z(2), a(1)
• To maximize lexicographical value, you'd want to use 'z' first, then 'c', then 'a'
• But you can't use more than repeatLimit consecutive occurrences of any character

The strategy involves greedily selecting the largest available character while respecting the repeat limit constraint. When you hit the limit for a character, you need to insert a different character before continuing with the original character.

Intuition

To create the lexicographically largest string, we want to use characters in descending order (z, y, x, ... , a) as much as possible. The greedy approach would be to always pick the largest available character.

However, we're constrained by the repeatLimit. When we've used a character repeatLimit times consecutively, we must "break" the sequence by inserting a different character before we can use the original character again.

Here's the key insight: When we need to break a sequence of the largest character, we should use the next largest available character as the "breaker" - but only one instance of it. Why? Because we want to get back to using the largest character as soon as possible.

Think of it like this:

• We have character counts stored (let's say 'z' appears 7 times, 'x' appears 2 times, and repeatLimit = 3)
• We use 'z' three times: "zzz"
• We still have 4 'z's left, but we can't use them consecutively
• We insert one 'x' as a breaker: "zzzx"
• Now we can use 'z' again for up to 3 more times: "zzzxzzz"
• We insert another 'x': "zzzxzzzx"
• Finally, we use the last 'z': "zzzxzzzxz"

The algorithm naturally falls out from this observation:

1. Count frequency of each character
2. Start from the largest character (index 25 for 'z')
3. Use as many of this character as allowed (up to repeatLimit or until exhausted)
4. If we still have more of this character, find the next largest available character to use as a breaker
5. Use exactly one instance of the breaker character
6. Repeat until we can't find any breaker characters or all characters are used

This greedy strategy ensures we always maintain the lexicographically largest possible string at each step.

Learn more about Greedy and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows the greedy strategy we identified:

Step 1: Character Frequency Counting

cnt = [0] * 26
for c in s:
    cnt[ord(c) - ord("a")] += 1

We create an array cnt of size 26 to store the frequency of each character. Each index represents a letter ('a' at index 0, 'b' at index 1, ..., 'z' at index 25).

Step 2: Build the Result String We iterate through characters from largest to smallest (index 25 to 0):

ans = []
j = 24  # Pointer for the "breaker" character
for i in range(25, -1, -1):
    j = min(i - 1, j)  # Ensure j is always less than i

Step 3: Main Logic for Each Character For each character at index i, we use a while loop to handle all occurrences:

while 1:
    x = min(repeatLimit, cnt[i])  # Take at most repeatLimit characters
    cnt[i] -= x
    ans.append(ascii_lowercase[i] * x)
  
    if cnt[i] == 0:  # All characters used, move to next
        break

Step 4: Handle the Breaker Character When we still have characters left after using repeatLimit of them, we need a breaker:

while j >= 0 and cnt[j] == 0:
    j -= 1  # Find the next available smaller character

if j < 0:  # No breaker available
    break

cnt[j] -= 1
ans.append(ascii_lowercase[j])  # Use exactly one breaker

Key Implementation Details:

1. Two-pointer technique: Variable i tracks the current largest character we're trying to use, while j tracks the next largest available character to use as a breaker.

2. Greedy selection: We always take min(repeatLimit, cnt[i]) characters at once, maximizing the use of larger characters.

3. Breaker optimization: We only use one character as a breaker each time, allowing us to return to the larger character immediately.

4. Early termination: If no breaker character is available (j < 0), we stop even if we have remaining characters of type i, as we cannot use them without violating the repeat limit.

The final result is constructed by joining all the character segments: "".join(ans).

This approach ensures O(n) time complexity where n is the length of the input string, as we process each character once during counting and once during construction.

Example Walkthrough

Let's walk through a concrete example with s = "cczazcc" and repeatLimit = 2.

Step 1: Count character frequencies

• c: 4 occurrences
• z: 2 occurrences
• a: 1 occurrence
• Array representation: cnt = [1, 0, 4, ..., 0, 2] (indices 0='a', 2='c', 25='z')

Step 2: Process characters from largest to smallest

Starting with i=25 (character 'z'), j=24:

• We have 2 'z's available
• Take min(2, 2) = 2 characters
• Result: "zz"
• cnt[25] = 0 (all 'z's used)
• Move to next character

Moving to i=2 (character 'c'), j=1:

• We have 4 'c's available
• Take min(2, 4) = 2 characters (repeatLimit is 2)
• Result: "zzcc"
• cnt[2] = 2 (2 'c's remaining)
• Still have 'c's left, need a breaker!

Finding breaker character:

• j starts at 1, check cnt[1]=0 (no 'b'), move j to 0
• cnt[0]=1 (we have 'a'!)
• Use 1 'a' as breaker
• Result: "zzcca"
• cnt[0] = 0

Continue with 'c':

• Take min(2, 2) = 2 remaining 'c's
• Result: "zzccacc"
• cnt[2] = 0 (all 'c's used)

Final Result: "zzccacc"

This is lexicographically largest because:

1. We used the largest available character ('z') first
2. When we hit the repeat limit for 'c', we used the next available character ('a') as a minimal breaker
3. We maximized the use of larger characters while respecting the consecutive repeat constraint

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + |Σ|)

The algorithm consists of several parts:

• Counting character frequencies: O(n) where n is the length of string s
• The main loop iterates through all 26 letters from 'z' to 'a': O(|Σ|) where |Σ| = 26
• Inside the main loop:
  • The inner while loop for each character i runs at most cnt[i] times in total
  • The inner while loop searching for valid j moves through the alphabet at most once overall
  • String concatenation operations append characters proportional to the input size
• The total number of characters appended equals n (the original string length)

Since we process each character from the input exactly once and iterate through the alphabet a constant number of times, the overall time complexity is O(n + |Σ|) where |Σ| = 26.

Space Complexity: O(|Σ|)

The algorithm uses:

• cnt array of size 26 to store character frequencies: O(|Σ|)
• ans list to build the result string: O(n) in the worst case, but this is typically not counted as extra space since it's the output
• A few integer variables (i, j, x): O(1)

The dominant extra space used (excluding the output) is the frequency array, giving us a space complexity of O(|Σ|) where |Σ| = 26.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Inefficient Separator Character Selection

Issue: A common mistake is resetting the separator search from the beginning (index 24 or current_idx - 1) every time we need a breaker character. This leads to unnecessary iterations through already exhausted characters.

Wrong Approach:

# Inefficient - starts search from scratch each time
for current_idx in range(25, -1, -1):
    while char_count[current_idx] > 0:
        # ... add characters ...
        if char_count[current_idx] > 0:
            # Wrong: Always starting from current_idx - 1
            for j in range(current_idx - 1, -1, -1):
                if char_count[j] > 0:
                    char_count[j] -= 1
                    result.append(chr(ord('a') + j))
                    break

Solution: Maintain a persistent separator pointer that doesn't reset, only moving backward when necessary. This ensures O(26) total iterations for finding separators across the entire algorithm.

Pitfall 2: Using Multiple Separator Characters

Issue: When breaking a sequence, using more than one separator character at a time wastes larger characters that could be used later in blocks.

Wrong Approach:

# Using too many separators reduces the final string's lexicographical value
if char_count[current_idx] > 0:
    # Wrong: Using multiple separators unnecessarily
    separators_needed = min(char_count[separator_idx], 2)  # Or any number > 1
    char_count[separator_idx] -= separators_needed
    result.append(chr(ord('a') + separator_idx) * separators_needed)

Solution: Always use exactly ONE separator character. This maximizes the opportunity to return to using the larger character immediately after the break.

Pitfall 3: Not Handling Early Termination Properly

Issue: Continuing to process when no valid separator exists can lead to violations of the repeat limit or infinite loops.

Wrong Approach:

while char_count[current_idx] > 0:
    chars_to_add = min(repeatLimit, char_count[current_idx])
    char_count[current_idx] -= chars_to_add
    result.append(chr(ord('a') + current_idx) * chars_to_add)
  
    # Wrong: Not checking if separator exists before trying to use current character again
    if char_count[current_idx] > 0:
        # Might not find any separator but continues anyway
        char_count[separator_idx] -= 1  # Could be accessing invalid index
        result.append(chr(ord('a') + separator_idx))

Solution: Always check if a valid separator exists (separator_idx >= 0) before attempting to continue with the current character. If no separator is available, break from the loop even if characters remain unused.

Pitfall 4: Incorrect Separator Index Initialization

Issue: Setting the separator index incorrectly can lead to attempting to use a character larger than or equal to the current character as a separator.

Wrong Approach:

for current_idx in range(25, -1, -1):
    # Wrong: separator could be >= current_idx
    separator_idx = 25  # Or not updating it at all

Solution: Always ensure separator_idx = min(current_idx - 1, separator_idx) at the start of processing each character. This guarantees the separator is lexicographically smaller than the current character being processed.