Construct String With Repeat Limit - Solution & Explanation
Problem Statement
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 <= 105sconsists of lowercase English letters.
Approach Overview
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 1: Greedy Approach with Frequency Count
This approach involves maintaining a frequency count of each character in the input string. We can then iterate over the characters in reverse lexicographical order, attempting to add each character to the result while respecting the repeatLimit. If the repeat limit is reached for a character, we temporarily insert the next available smaller character to break the sequence. We continue this process until all valid characters have been used.
The solution involves counting the frequency of each character in the input string. We then iterate from 'z' to 'a', adding as many of the current character as the repeat limit allows, before adding the next highest available character to break any excessive repetition. This continues until all characters are used according to the rules.
Complexity
Time Complexity: O(n + m), where n is the length of the string and m = 26, the number of letters in the alphabet.
Space Complexity: O(1), as the frequency array size is fixed.
Approach 2: Greedy Algorithm
First, we use an array cnt of length 26 to count the number of occurrences of each character in string s. Then, we enumerate the ith letter of the alphabet in descending order, each time taking out at most min(cnt[i], repeatLimit) of letter i. If after taking them out cnt[i] is still greater than 0, we continue to take the jth letter of the alphabet, where j is the largest index satisfying j < i and cnt[j] > 0, until all letters are taken.
The time complexity is O(n + |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of string s, and \Sigma is the character set. In this problem, |\Sigma| = 26.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Frequency Count | Time Complexity: O(n + m), where n is the length of the string and m = 26, the number of letters in the alphabet. |
| Greedy Algorithm | ā |
Detailed Complexity Analysis
| 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 |
Video Solution
Construct String With Repeat Limit | 2 Simple Approaches | Leetcode 2182 | codestorywithMIK ā¢ codestorywithMIK ā¢ 7,815 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Construct String With Repeat Limit easy or hard?
Construct String With Repeat Limit Python/Java solution
How to solve Construct String With Repeat Limit in O(n)?
What is the best approach for Construct String With Repeat Limit?
Is Construct String With Repeat Limit asked at Google/Amazon/Meta?
What data structure is used in Construct String With Repeat Limit?
What is the time complexity of Construct String With Repeat Limit?
Ready to solve this problem?
Practice Construct String With Repeat Limit with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor