Construct String With Repeat Limit — Medium Problem & Solution

Using some or all of the characters of s, build the lexicographically largest string in which no character appears more than repeatLimit times in a row.

Difficulty: Medium
Topics: Strings, Hash Table, Greedy, Counting, Heap
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Using some or all of the characters of s, build the lexicographically largest string in which no character appears more than repeatLimit times in a row.

Return that string.

Example 1

Input: s = "codekairo", repeatLimit = 2
Output: rookiedca
Explanation: Largest first: `r`, then both `o`s (exactly the limit), then the rest descending.

Example 2

Input: s = "cczazcc", repeatLimit = 3
Output: zzcccac
Explanation: After three `c`s the run must break, so the lone `a` goes in before the last `c`.

Example 3

Input: s = "aababab", repeatLimit = 2
Output: bbabaa
Explanation: One `a` is left unused — you need not use every character.

Constraints

1 <= repeatLimit <= s.length <= 10^5
s consists of lowercase English letters.

How to solve Construct String With Repeat Limit

Count the letters, then repeatedly take the largest one still available, emitting up to repeatLimit copies. If it is not exhausted, insert exactly one copy of the next-largest available letter to break the run, and go back to the largest.

Approach

Tally the 26 letters.
Point i at the largest non-empty letter; emit min(count[i], repeatLimit) copies.
If count[i] reaches 0, move i down and continue.
Otherwise find the largest j < i with count[j] > 0; if none exists, stop. Emit one copy of j and repeat.

Why it works

The greedy is optimal because lexicographic order is decided at the first differing position: putting the largest possible character there can never be beaten later. The separator must be exactly one character and the largest one available — a longer break, or a smaller separator, both push a smaller character earlier than necessary. And when no smaller letter is left, the remaining copies genuinely cannot be used, which is why the output may be shorter than s.

Complexity

Time — O(n + 26²)
Space — O(1) beyond the output

Pitfalls

Insert exactly one separator, not repeatLimit of them.
The separator is the largest smaller available letter, not the smallest.
Some characters may go unused; the answer need not be a permutation of s.

Reference solution

Python

def repeatLimitedString(s: str, repeatLimit: int) -> str:
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - 97] += 1
    out = []
    i = 25
    while i >= 0:
        if cnt[i] == 0:
            i -= 1
            continue
        take = min(cnt[i], repeatLimit)
        out.append(chr(97 + i) * take)
        cnt[i] -= take
        if cnt[i] == 0:
            i -= 1
            continue
        j = i - 1
        while j >= 0 and cnt[j] == 0:
            j -= 1
        if j < 0:
            break
        out.append(chr(97 + j))
        cnt[j] -= 1
    return "".join(out)

JavaScript

var repeatLimitedString = function(s, repeatLimit) {
    var cnt = [], k;
    for (k = 0; k < 26; k++) cnt.push(0);
    for (k = 0; k < s.length; k++) cnt[s.charCodeAt(k) - 97]++;
    var out = "";
    var i = 25;
    while (i >= 0) {
        if (cnt[i] === 0) { i--; continue; }
        var take = Math.min(cnt[i], repeatLimit);
        for (var t = 0; t < take; t++) out += String.fromCharCode(97 + i);
        cnt[i] -= take;
        if (cnt[i] === 0) { i--; continue; }
        var j = i - 1;
        while (j >= 0 && cnt[j] === 0) j--;
        if (j < 0) break;
        out += String.fromCharCode(97 + j);
        cnt[j]--;
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue