Construct String With Repeat Limit
Problem
Given a string s and an integer repeatLimit, rearrange any subset of the letters of s (using each letter at most as many times as it occurs) into the lexicographically largest string such that no letter appears more than repeatLimit times in a row. You do not have to use every letter, but a valid answer always uses every letter exactly its full count, since dropping a letter never helps.
s = "cczazcc", repeatLimit = 3"zzcccac"import heapq
def repeat_limited_string(s, repeat_limit):
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - 97] += 1
h = [-i for i in range(26) if cnt[i] > 0]
heapq.heapify(h)
out = []
while h:
i = -heapq.heappop(h)
take = min(cnt[i], repeat_limit)
out.append(chr(i + 97) * take)
cnt[i] -= take
if cnt[i] > 0:
if not h:
break
j = -h[0]
out.append(chr(j + 97))
cnt[j] -= 1
if cnt[j] == 0:
heapq.heappop(h)
heapq.heappush(h, -i)
return ''.join(out)function repeatLimitedString(s, repeatLimit) {
const cnt = new Array(26).fill(0);
for (const ch of s) cnt[ch.charCodeAt(0) - 97]++;
const heap = [];
for (let i = 0; i < 26; i++) if (cnt[i] > 0) heap.push(i);
heap.sort((x, y) => y - x);
const out = [];
while (heap.length) {
const i = heap.shift();
const take = Math.min(cnt[i], repeatLimit);
out.push(String.fromCharCode(97 + i).repeat(take));
cnt[i] -= take;
if (cnt[i] > 0) {
if (!heap.length) break;
const j = heap[0];
out.push(String.fromCharCode(97 + j));
cnt[j]--;
if (cnt[j] === 0) heap.shift();
heap.unshift(i);
}
}
return out.join('');
}class Solution {
public String repeatLimitedString(String s, int repeatLimit) {
int[] cnt = new int[26];
for (char ch : s.toCharArray()) cnt[ch - 'a']++;
PriorityQueue<Integer> heap = new PriorityQueue<>((x, y) -> y - x);
for (int i = 0; i < 26; i++) if (cnt[i] > 0) heap.offer(i);
StringBuilder out = new StringBuilder();
while (!heap.isEmpty()) {
int i = heap.poll();
int take = Math.min(cnt[i], repeatLimit);
for (int k = 0; k < take; k++) out.append((char) ('a' + i));
cnt[i] -= take;
if (cnt[i] > 0) {
if (heap.isEmpty()) break;
int j = heap.peek();
out.append((char) ('a' + j));
cnt[j]--;
if (cnt[j] == 0) heap.poll();
heap.offer(i);
}
}
return out.toString();
}
}string repeatLimitedString(string s, int repeatLimit) {
vector<int> cnt(26, 0);
for (char ch : s) cnt[ch - 'a']++;
priority_queue<int> heap;
for (int i = 0; i < 26; i++) if (cnt[i] > 0) heap.push(i);
string out;
while (!heap.empty()) {
int i = heap.top();
heap.pop();
int take = min(cnt[i], repeatLimit);
out.append(take, (char)('a' + i));
cnt[i] -= take;
if (cnt[i] > 0) {
if (heap.empty()) break;
int j = heap.top();
out.push_back((char)('a' + j));
cnt[j]--;
if (cnt[j] == 0) heap.pop();
heap.push(i);
}
}
return out;
}Explanation
To make the result lexicographically largest, we always want the biggest possible letter as early as possible. So at every step we reach for the largest letter still available. A max-heap of the present letters (or just a scan over 26 buckets) hands us that letter instantly.
We emit that top letter as many times as we can — but no more than repeatLimit in a row. So we append min(count, repeatLimit) copies and drop its count by that much.
After that, one of two things is true. If the letter is now used up, we remove it from the heap and continue with the next-largest. If copies still remain, it means we stopped because we hit the cap — appending another would violate the limit. To break the run, we borrow exactly one copy of the next-largest letter and append it. That single different letter resets the run, and on the next loop the top letter is free to be used again.
If we hit the cap but there is no second letter left to break the run, we must stop — the remaining copies of the top letter cannot be placed.
Example: s = "cczazcc", repeatLimit = 3 → counts c:4, z:2, a:1. The largest letter is 'z', and we have 2 (under the cap), so we lay down "zz". Next is 'c' with 4 copies; we emit 3 ("ccc") and stop at the cap with one 'c' left. To break the run we borrow one 'a', giving "zzccca". Now 'c' is free again and we place the last one: "zzcccac".