Construct String With Repeat Limit

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.

Examples

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^5
s consists of lowercase English letters.

Solution

Method 1 - Using Maxheap

To maximize the lexicographical order, we append the characters in sorted order starting from the largest character.
We keep track of the number of consecutive additions of the current character and switch characters when we reach the specified repeatLimit.

Here is the approach:

Count the frequency of each character.
Sort the characters in descending order.
Append characters to the result string while ensuring no character exceeds the repeatLimit. If the limit is reached, insert a smaller character to break the sequence.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java

class Solution {
    public String repeatLimitedString(String s, int repeatLimit) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        PriorityQueue<Character> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                maxHeap.add((char) (i + 'a'));
            }
        }

        StringBuilder ans = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            char curr = maxHeap.poll();
            int count = Math.min(freq[curr - 'a'], repeatLimit);
            for (int i = 0; i < count; i++) {
                ans.append(curr);
            }
            freq[curr - 'a'] -= count;
            
            if (freq[curr - 'a'] > 0) {
                if (maxHeap.isEmpty()) {
                    break;
                }

                char next = maxHeap.poll();
                ans.append(next);
                freq[next - 'a']--;
                
                if (freq[next - 'a'] > 0) {
                    maxHeap.add(next);
                }
                maxHeap.add(curr);
            }
        }

        return ans.toString();
    }
}

Python

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        freq = Counter(s)
        max_heap = [-ord(c) for c in freq]
        heapify(max_heap)
        
        ans: List[str] = []

        while max_heap:
            curr = chr(-heappop(max_heap))
            count = min(freq[curr], repeatLimit)
            ans.extend([curr] * count)
            freq[curr] -= count
            
            if freq[curr] > 0:
                if not max_heap:
                    break

                next_char = chr(-heappop(max_heap))
                ans.append(next_char)
                freq[next_char] -= 1
                
                if freq[next_char] > 0:
                    heappush(max_heap, -ord(next_char))
                heappush(max_heap, -ord(curr))
        
        return ''.join(ans)

Complexity

⏰ Time complexity: O(n + k log k) = O(n)
- n is the length of the input string for counting character frequencies.
- k is the number of distinct characters (at most 26 for lowercase English letters).
- log(k) is due to sorting the characters.
🧺 Space complexity: O(n + k)
- n for the answer storage
- k for storing characters and their counts.