Watch 10 video solutions for Construct String With Repeat Limit, a medium level problem involving Hash Table, String, Greedy. This walkthrough by codestorywithMIK has 7,657 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You are given a string s and an integer repeatLimit. The goal is to build the lexicographically largest possible string using characters from s, while ensuring no character appears more than repeatLimit times consecutively.
Approach 1: Brute Force with Re-Sorting (O(n² log n) time, O(n) space)
One straightforward idea is to repeatedly choose the largest valid character and append it to the result. After each append, rebuild or sort the remaining characters to find the next candidate. If the largest character violates the repeat limit, temporarily pick the next largest character to break the sequence. This works logically but becomes inefficient because sorting or scanning the remaining characters happens many times. The approach demonstrates the greedy intuition but is too slow for large inputs.
Approach 2: Greedy with Max Heap (O(n log k) time, O(k) space)
Use a frequency map and push characters into a max heap ordered by lexicographic value. Always pop the largest character and append it up to repeatLimit times. If more occurrences remain, you must insert a smaller character next to reset the repetition constraint. Pop the next largest character from the heap, append it once, then push the original character back if it still has remaining frequency. The heap guarantees you always pick the best available character. This approach uses Heap (Priority Queue) to manage ordering dynamically.
Approach 3: Greedy with Frequency Count (O(n + 26) time, O(26) space)
The optimal approach leverages the small alphabet size. Count frequencies of all characters using a fixed array. Start from the largest character ('z') and append it up to repeatLimit times. If more copies remain, find the next smaller character with available frequency and insert it once to break the repetition chain. Continue iterating from the largest character again. Because the alphabet is limited to 26 letters, scanning for the next valid character is constant time. This approach combines Greedy decision making with simple Counting, making it both fast and memory efficient.
Recommended for interviews: The greedy frequency-count solution is what most interviewers expect. It demonstrates that you recognize the lexicographic priority and exploit the fixed alphabet to avoid heavier data structures. Mentioning the heap-based greedy approach first shows understanding of the general strategy, while implementing the constant-space counting version shows optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Re-Sorting | O(n² log n) | O(n) | Conceptual understanding of greedy character selection |
| Greedy with Max Heap | O(n log k) | O(k) | General solution when alphabet size or options are dynamic |
| Greedy with Frequency Count | O(n + 26) | O(26) | Optimal solution for lowercase letters with fixed alphabet |