Construct String With Repeat Limit

Medium
1032.

Construct String With Repeat Limit

Construct String With Repeat Limit is a medium coding problem on strings, hash table and greedy, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} repeatLimit
 * @return {string}
 */
var repeatLimitedString = function(s, repeatLimit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Construct String With Repeat Limit — Problem & Solution

Construct String With Repeat Limit solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Construct String With Repeat Limit is a medium coding problem on strings, hash table and greedy, asked in Amazon, Google and Microsoft interviews.

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.

Hints for Construct String With Repeat Limit

  1. Hint 1

    Greedily emit the largest available character, up to repeatLimit copies.

  2. Hint 2

    If that character still has copies left, you must break the run with exactly one copy of the next-largest available character.

  3. Hint 3

    If no smaller character remains, you are finished — the leftovers cannot be placed.

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

  1. Tally the 26 letters.
  2. Point i at the largest non-empty letter; emit min(count[i], repeatLimit) copies.
  3. If count[i] reaches 0, move i down and continue.
  4. 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)

Java

public static String repeatLimitedString(String s, int repeatLimit) {
    int[] cnt = new int[26];
    for (int k = 0; k < s.length(); k++) cnt[s.charAt(k) - 'a']++;
    StringBuilder sb = new StringBuilder();
    int i = 25;
    while (i >= 0) {
        if (cnt[i] == 0) { i--; continue; }
        int take = Math.min(cnt[i], repeatLimit);
        for (int t = 0; t < take; t++) sb.append((char) ('a' + i));
        cnt[i] -= take;
        if (cnt[i] == 0) { i--; continue; }
        int j = i - 1;
        while (j >= 0 && cnt[j] == 0) j--;
        if (j < 0) break;
        sb.append((char) ('a' + j));
        cnt[j]--;
    }
    return sb.toString();
}

C++

string repeatLimitedString(string s, int repeatLimit) {
    vector<int> cnt(26, 0);
    for (char c : s) cnt[c - 'a']++;
    string out;
    int i = 25;
    while (i >= 0) {
        if (cnt[i] == 0) { i--; continue; }
        int take = min(cnt[i], repeatLimit);
        out.append((size_t) take, (char) ('a' + i));
        cnt[i] -= take;
        if (cnt[i] == 0) { i--; continue; }
        int j = i - 1;
        while (j >= 0 && cnt[j] == 0) j--;
        if (j < 0) break;
        out += (char) ('a' + j);
        cnt[j]--;
    }
    return 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets