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 <= 105s consists of lowercase English letters.To solve #2182 Construct String With Repeat Limit, the goal is to build the lexicographically largest string while ensuring that no character repeats more than repeatLimit times consecutively. A common strategy is to combine frequency counting with a greedy selection process.
First, count how many times each character appears. Then repeatedly pick the largest available character (lexicographically) to append to the result. You can add the same character up to repeatLimit times. If more occurrences remain, you must temporarily insert the next largest different character to break the sequence before continuing.
A max heap (priority queue) works well for efficiently selecting the largest available character at each step. If the current character cannot be used due to the repeat limit, the algorithm briefly switches to the next best option.
This greedy approach ensures the final string remains as large as possible lexicographically while respecting the constraint. The overall complexity depends mainly on heap operations and character counts.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Max Heap and Frequency Counting | O(n log k) | O(k) |
| Greedy with Direct Frequency Array (26 letters) | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Start constructing the string in descending order of characters.
When repeatLimit is reached, pick the next largest character.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
When a character has already been used repeatLimit times consecutively but still has remaining frequency, the algorithm inserts the next largest different character. This breaks the repetition constraint and allows the larger character to be used again later.
Yes, variations of greedy string construction and heap-based problems are common in FAANG-style interviews. This problem tests understanding of greedy decisions, frequency counting, and priority queue usage.
A max heap (priority queue) is commonly used because it allows quick access to the largest available character. In cases where the character set is fixed (like lowercase English letters), a simple frequency array with pointer scanning can also work efficiently.
The optimal approach uses a greedy strategy combined with character frequency counting. By always choosing the largest available character and respecting the repeat limit, you can construct the lexicographically largest valid string. A max heap or frequency array helps efficiently select the next character.