Construct String With Repeat Limit

Med

#1987Time: 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.2 companies

Patterns

Greedy Counting

Data structures

Hash Table String Heap (Priority Queue)

Companies

Arista Networks Fortinet

Prompt

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 <= 10⁵
s consists of lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public String repeatLimitedString(String s, int repeatLimit) {3        int[] counts = new int[26];4        for (char c : s.toCharArray()) {5            counts[c - 'a']++;6        }7 8        StringBuilder result = new StringBuilder();9        int consecutive = 0;10        char lastChar = '#';11 12        // The total length of the result can't exceed s.length()13        for (int k = 0; k < s.length(); k++) {14            boolean foundChar = false;15            // Iterate from z to a to find the next character to append16            for (int i = 25; i >= 0; i--) {17                char currentChar = (char) ('a' + i);18                if (counts[i] > 0) {19                    // Check if we can append this character20                    if (currentChar == lastChar && consecutive >= repeatLimit) {21                        continue; // Cannot append, try next smaller char22                    }23 24                    // Append the character25                    result.append(currentChar);26                    counts[i]--;27                    28                    if (currentChar == lastChar) {29                        consecutive++;30                    } else {31                        lastChar = currentChar;32                        consecutive = 1;33                    }34                    35                    foundChar = true;36                    break; // Found the largest possible char for this position37                }38            }39 40            if (!foundChar) {41                // No more characters can be appended42                break;43            }44        }45 46        return result.toString();47    }48}

Complexity

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.

Trade-offs

Pros

Simple to understand and implement.

Cons

Inefficient due to the repeated scanning of the alphabet for every single character added to the result.

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.

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.

Walkthrough

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.

1class Solution {2    public String repeatLimitedString(String s, int repeatLimit) {3        int[] counts = new int[26];4        for (char c : s.toCharArray()) {5            counts[c - 'a']++;6        }7 8        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);9        for (int i = 0; i < 26; i++) {10            if (counts[i] > 0) {11                maxHeap.offer(new int[]{i, counts[i]});12            }13        }14 15        StringBuilder result = new StringBuilder();16        while (!maxHeap.isEmpty()) {17            int[] top = maxHeap.poll();18            int charIndex = top[0];19            int count = top[1];20            char currentChar = (char) ('a' + charIndex);21 22            int appendCount = Math.min(count, repeatLimit);23            for (int i = 0; i < appendCount; i++) {24                result.append(currentChar);25            }26 27            int remainingCount = count - appendCount;28            if (remainingCount > 0) {29                if (maxHeap.isEmpty()) {30                    break; // No other char to break the sequence31                }32                33                int[] nextTop = maxHeap.poll();34                int nextCharIndex = nextTop[0];35                int nextCount = nextTop[1];36                char nextChar = (char) ('a' + nextCharIndex);37                38                result.append(nextChar);39                40                // Add the next char back if it's not used up41                if (nextCount > 1) {42                    maxHeap.offer(new int[]{nextCharIndex, nextCount - 1});43                }44                45                // Add the original char back46                maxHeap.offer(new int[]{charIndex, remainingCount});47            }48        }49        return result.toString();50    }51}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public String repeatLimitedString(String s, int repeatLimit) {3        int[] counts = new int[26];4        for (char c : s.toCharArray()) {5            counts[c - 'a']++;6        }7 8        StringBuilder result = new StringBuilder();9        int i = 25; // Pointer for the current character ('z')10        int j = 24; // Pointer for the separator character11 12        while (i >= 0) {13            if (counts[i] == 0) {14                i--;15                continue;16            }17 18            // Append the current character up to repeatLimit times19            int k = Math.min(counts[i], repeatLimit);20            for (int iter = 0; iter < k; iter++) {21                result.append((char) ('a' + i));22            }23            counts[i] -= k;24 25            // If we still have more of char 'i', we need a separator26            if (counts[i] > 0) {27                // j should be less than i28                if (j >= i) j = i - 1;29                30                // Find the next available character for separator31                while (j >= 0 && counts[j] == 0) {32                    j--;33                }34                35                // If a separator is found36                if (j >= 0) {37                    result.append((char) ('a' + j));38                    counts[j]--;39                } else {40                    // No separator found, we are done41                    break;42                }43            }44        }45        return result.toString();46    }47}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 (); } }

1class 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 ; } };

1class 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 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 (); } }

1class 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 ; } };

1class 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 )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.