# Construct String With Repeat Limit **Difficulty:** MEDIUM [External](https://leetcode.com/problems/construct-string-with-repeat-limit) Canonical: https://scaleengineer.com/dsa/problems/construct-string-with-repeat-limit **Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting) **Data structures:** Hash Table, String, Heap (Priority Queue) **Companies:** [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Fortinet](https://scaleengineer.com/companies/fortinet) --- ## Problem 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 <= 105` * `s` consists of lowercase English letters. # Approaches ## Naive Greedy Approach This is a straightforward greedy approach. To build the lexicographically largest string, at each step, we want to append the largest possible character available. We maintain a count of consecutive characters appended. If we can't append the largest character because we've hit the `repeatLimit`, we try to append the second-largest, and so on. This process is repeated for each position in the resulting string. **Time:** O(N * C), where N is the length of `s` and C is the alphabet size (26). For each of the up to `N` characters we append to the result, we might scan through all `C` characters to find the best one. · **Space:** O(N), where N is the length of the input string `s`. This is for the `StringBuilder` used to construct the result. The frequency map takes O(C) or O(1) space. **Pros:** Simple to understand and implement. **Cons:** Inefficient due to the repeated scanning of the alphabet for every single character added to the result. ### Explanation This method works by repeatedly finding the best possible character to append next. For each position in the output string, it scans all possible characters from 'z' down to 'a'. It picks the first one that is available (count > 0) and does not violate the `repeatLimit` constraint with the previously appended character. While simple to conceptualize, this repeated scanning leads to a higher time complexity, as the search for the best character is performed for every character in the output string. ```java class Solution { public String repeatLimitedString(String s, int repeatLimit) { int[] counts = new int[26]; for (char c : s.toCharArray()) { counts[c - 'a']++; } StringBuilder result = new StringBuilder(); int consecutive = 0; char lastChar = '#'; // The total length of the result can't exceed s.length() for (int k = 0; k < s.length(); k++) { boolean foundChar = false; // Iterate from z to a to find the next character to append for (int i = 25; i >= 0; i--) { char currentChar = (char) ('a' + i); if (counts[i] > 0) { // Check if we can append this character if (currentChar == lastChar && consecutive >= repeatLimit) { continue; // Cannot append, try next smaller char } // Append the character result.append(currentChar); counts[i]--; if (currentChar == lastChar) { consecutive++; } else { lastChar = currentChar; consecutive = 1; } foundChar = true; break; // Found the largest possible char for this position } } if (!foundChar) { // No more characters can be appended break; } } return result.toString(); } } ``` ### Algorithm * Calculate the frequency of each character in `s` and store it in an array `counts`. * Initialize an empty `StringBuilder` `result`. * Initialize `consecutiveCount = 0` and `lastChar = '#'`. * Enter a loop that continues as long as we can add characters to `result`. A simple way is to loop up to `s.length()` times, as the result cannot be longer. * Inside the loop, iterate from `i = 25` down to `0` (from 'z' to 'a') to find the best character to append. * For a character `currentChar` corresponding to `i`, if its count is positive (`counts[i] > 0`): * Check if we can append it. We can if `currentChar` is not the same as `lastChar`, or if `consecutiveCount < repeatLimit`. * If we can append it, add it to `result`, decrement its count in `counts`, update `lastChar` and `consecutiveCount`, and break the inner loop (from 'z' to 'a') since we've made the best possible choice for the current position. * If the inner loop completes without finding any character to append, it means we are done. Break the outer loop. * Return the string from `result`. ## Greedy Approach with Max Heap This approach improves upon the naive greedy method by using a max heap (Priority Queue) to efficiently find the largest and second-largest available characters. Instead of scanning the alphabet repeatedly, we can retrieve the best character in `O(log C)` time, where C is the alphabet size. We process characters in chunks, appending the largest available character up to `repeatLimit` times, and then using the second-largest as a separator if needed. **Time:** O(N + K * log C), where N is for the initial count, C is the alphabet size (26), and K is the number of character groups formed. K is at most `N/repeatLimit`. Since C is a constant, this simplifies to O(N). · **Space:** O(N). The `StringBuilder` can grow up to size N. The heap and frequency map take O(C) space, which is constant. **Pros:** Much more efficient than the naive scan, as finding the next best character is fast (`O(log C)`). **Cons:** Slightly more complex to implement due to the use of a priority queue.; Has a slightly higher constant factor in time complexity compared to the two-pointer approach due to heap operations. ### Explanation The core idea is to maintain the available characters in a data structure that always gives us the largest one quickly. A max heap is perfect for this. We populate the heap with characters and their counts. The main loop of the algorithm repeatedly extracts the largest character, appends it in a block, and if the repeat limit is reached, it extracts the second-largest character to act as a separator before re-inserting the first character back into the heap for future use. This avoids the costly linear scan of the naive approach. ```java class Solution { public String repeatLimitedString(String s, int repeatLimit) { int[] counts = new int[26]; for (char c : s.toCharArray()) { counts[c - 'a']++; } PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]); for (int i = 0; i < 26; i++) { if (counts[i] > 0) { maxHeap.offer(new int[]{i, counts[i]}); } } StringBuilder result = new StringBuilder(); while (!maxHeap.isEmpty()) { int[] top = maxHeap.poll(); int charIndex = top[0]; int count = top[1]; char currentChar = (char) ('a' + charIndex); int appendCount = Math.min(count, repeatLimit); for (int i = 0; i < appendCount; i++) { result.append(currentChar); } int remainingCount = count - appendCount; if (remainingCount > 0) { if (maxHeap.isEmpty()) { break; // No other char to break the sequence } int[] nextTop = maxHeap.poll(); int nextCharIndex = nextTop[0]; int nextCount = nextTop[1]; char nextChar = (char) ('a' + nextCharIndex); result.append(nextChar); // Add the next char back if it's not used up if (nextCount > 1) { maxHeap.offer(new int[]{nextCharIndex, nextCount - 1}); } // Add the original char back maxHeap.offer(new int[]{charIndex, remainingCount}); } } return result.toString(); } } ``` ### Algorithm * Calculate character frequencies and store them in an array `counts`. * Create a max heap (`PriorityQueue` in Java) and populate it with all characters that have a count greater than zero. The heap should store pairs of `[character_index, count]` and prioritize larger characters. * Initialize an empty `StringBuilder` `result`. * Loop while the heap is not empty. * In each iteration, extract the character with the highest priority (`char1`) from the heap. * Append `char1` to the `result` up to `repeatLimit` times, or until we run out of `char1`. Let's say we append it `k` times. * Update the count of `char1`. * If we still have more of `char1` left (meaning we hit the `repeatLimit`), we need a separator. * Check if the heap is empty. If so, we can't add a separator and must stop. * If the heap is not empty, extract the next largest character (`char2`). Append it once to `result` and update its count. * If `char2` still has a positive count after being used once, add it back to the heap. * Finally, add `char1` (with its remaining count) back to the heap, as we can now use it again. * Return the string from `result`. ## Greedy Approach with Two Pointers This is the most optimized approach. It builds on the same greedy idea but uses two pointers to keep track of the current character and the next available character for separation, avoiding both repeated scans and the overhead of a heap. One pointer, `i`, points to the current largest character we are using. Another pointer, `j`, points to the next largest character available to be a separator. Since these pointers only ever move downwards through the alphabet, the total work to find characters is minimal. **Time:** O(N + C). `N` for counting frequencies and building the string. The two pointers `i` and `j` traverse the alphabet (size `C`) at most once in total. Since `C` is a constant 26, the complexity is linear, O(N). · **Space:** O(N). The `StringBuilder` can grow up to size N. The frequency map takes O(C) space, which is constant. **Pros:** Highly efficient with linear time complexity and low constant factors.; Avoids the overhead of a priority queue. **Cons:** The logic with two pointers might be slightly less intuitive to come up with than the heap-based solution. ### Explanation This approach refines the greedy strategy to its most efficient form. After counting frequencies, we use a pointer `i` to track the main character we're appending, starting from 'z'. We append this character in blocks of size up to `repeatLimit`. If a block is appended and we still have more of character `i`, we need a separator. We use a second pointer `j` (initialized to `i-1`) to find the next largest available character. Crucially, `i` and `j` never increase; they only scan down the alphabet once over the entire execution of the algorithm. This eliminates the `log C` factor from the heap solution and the `C` factor from the naive solution, resulting in a true linear time complexity with a very small constant factor. ```java class Solution { public String repeatLimitedString(String s, int repeatLimit) { int[] counts = new int[26]; for (char c : s.toCharArray()) { counts[c - 'a']++; } StringBuilder result = new StringBuilder(); int i = 25; // Pointer for the current character ('z') int j = 24; // Pointer for the separator character while (i >= 0) { if (counts[i] == 0) { i--; continue; } // Append the current character up to repeatLimit times int k = Math.min(counts[i], repeatLimit); for (int iter = 0; iter < k; iter++) { result.append((char) ('a' + i)); } counts[i] -= k; // If we still have more of char 'i', we need a separator if (counts[i] > 0) { // j should be less than i if (j >= i) j = i - 1; // Find the next available character for separator while (j >= 0 && counts[j] == 0) { j--; } // If a separator is found if (j >= 0) { result.append((char) ('a' + j)); counts[j]--; } else { // No separator found, we are done break; } } } return result.toString(); } } ``` ### Algorithm * Calculate character frequencies in an array `counts`. * Initialize a `StringBuilder` `result`. * Initialize two pointers: `i = 25` (for the main character, starting at 'z') and `j = 24` (for the separator, starting at 'y'). * Loop as long as `i >= 0`. * If the count for character `i` is zero, it's exhausted. Decrement `i` to move to the next largest character and continue. * Append character `i` up to `repeatLimit` times, or until it runs out. Let's say we append it `k` times. * Update the count of character `i`. * If character `i` is still not exhausted (`counts[i] > 0`), it means we hit the `repeatLimit` and need a separator. * Use pointer `j` to find the next available separator. We ensure `j` is less than `i` and move it downwards only when the character at `j` is unavailable (`counts[j] == 0`). * If a separator `j` is found, append it once, decrement its count, and continue the main loop with the same `i`. * If no separator `j` can be found (`j` becomes negative), we cannot break the sequence of character `i`, so we must stop. Break the loop. * Return the string from `result`. # Solutions ### Java ```java class Solution { public String repeatLimitedString ( String s , int repeatLimit ) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < s . length (); ++ i ) { ++ cnt [ s . charAt ( i ) - 'a' ]; } StringBuilder ans = new StringBuilder (); for ( int i = 25 , j = 24 ; i >= 0 ; -- i ) { j = Math . min ( j , i - 1 ); while ( true ) { for ( int k = Math . min ( cnt [ i ], repeatLimit ); k > 0 ; -- k ) { ans . append (( char ) ( 'a' + i )); -- cnt [ i ]; } if ( cnt [ i ] == 0 ) { break ; } while ( j >= 0 && cnt [ j ] == 0 ) { -- j ; } if ( j < 0 ) { break ; } ans . append (( char ) ( 'a' + j )); -- cnt [ j ]; } } return ans . toString (); } } ``` ### CPP ```cpp class Solution { public: string repeatLimitedString ( string s , int repeatLimit ) { int cnt [ 26 ]{}; for ( char & c : s ) { ++ cnt [ c - 'a' ]; } string ans ; for ( int i = 25 , j = 24 ; ~ i ; -- i ) { j = min ( j , i - 1 ); while ( 1 ) { for ( int k = min ( cnt [ i ], repeatLimit ); k ; -- k ) { ans += 'a' + i ; -- cnt [ i ]; } if ( cnt [ i ] == 0 ) { break ; } while ( j >= 0 && cnt [ j ] == 0 ) { -- j ; } if ( j < 0 ) { break ; } ans += 'a' + j ; -- cnt [ j ]; } } return ans ; } }; ``` ### Python ```python class Solution : def repeatLimitedString ( self , s : str , repeatLimit : int ) -> str : cnt = [ 0 ] * 26 for c in s : cnt [ ord ( c ) - ord ( "a" )] += 1 ans = [] j = 24 for i in range ( 25 , - 1 , - 1 ): j = min ( i - 1 , j ) while 1 : x = min ( repeatLimit , cnt [ i ]) cnt [ i ] -= x ans . append ( ascii_lowercase [ i ] * x ) if cnt [ i ] == 0 : break while j >= 0 and cnt [ j ] == 0 : j -= 1 if j < 0 : break cnt [ j ] -= 1 ans . append ( ascii_lowercase [ j ]) return "" . join ( ans ) ```