2182. Construct String With Repeat Limit - Solution

The 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.

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.

Approach overview

Problem Overview: You are given a string s and an integer repeatLimit. The goal is to build the lexicographically largest possible string using characters from s, while ensuring no character appears more than repeatLimit times consecutively.

Approach 1: Brute Force with Re-Sorting (O(n² log n) time, O(n) space)

One straightforward idea is to repeatedly choose the largest valid character and append it to the result. After each append, rebuild or sort the remaining characters to find the next candidate. If the largest character violates the repeat limit, temporarily pick the next largest character to break the sequence. This works logically but becomes inefficient because sorting or scanning the remaining characters happens many times. The approach demonstrates the greedy intuition but is too slow for large inputs.

Approach 2: Greedy with Max Heap (O(n log k) time, O(k) space)

Use a frequency map and push characters into a max heap ordered by lexicographic value. Always pop the largest character and append it up to repeatLimit times. If more occurrences remain, you must insert a smaller character next to reset the repetition constraint. Pop the next largest character from the heap, append it once, then push the original character back if it still has remaining frequency. The heap guarantees you always pick the best available character. This approach uses Heap (Priority Queue) to manage ordering dynamically.

Approach 3: Greedy with Frequency Count (O(n + 26) time, O(26) space)

The optimal approach leverages the small alphabet size. Count frequencies of all characters using a fixed array. Start from the largest character ('z') and append it up to repeatLimit times. If more copies remain, find the next smaller character with available frequency and insert it once to break the repetition chain. Continue iterating from the largest character again. Because the alphabet is limited to 26 letters, scanning for the next valid character is constant time. This approach combines Greedy decision making with simple Counting, making it both fast and memory efficient.

Recommended for interviews: The greedy frequency-count solution is what most interviewers expect. It demonstrates that you recognize the lexicographic priority and exploit the fixed alphabet to avoid heavier data structures. Mentioning the heap-based greedy approach first shows understanding of the general strategy, while implementing the constant-space counting version shows optimization skills.

Approach 1: Greedy Approach with Frequency Count

This approach involves maintaining a frequency count of each character in the input string. We can then iterate over the characters in reverse lexicographical order, attempting to add each character to the result while respecting the repeatLimit. If the repeat limit is reached for a character, we temporarily insert the next available smaller character to break the sequence. We continue this process until all valid characters have been used.

Python

def repeatLimitedString(s, repeatLimit):
    from collections import Counter
    count = Counter(s)
    result = []
    sorted_chars = sorted(count.keys(), reverse=True)
    i = 0
    while i < len(sorted_chars):
        char = sorted_chars[i]
        if count[char] > 0:
            use = min(repeatLimit, count[char])
            result.extend([char] * use)
            count[char] -= use
            if count[char] > 0:
                next_char_found = False
                for next_char in sorted_chars[i+1:]:
                    if count[next_char] > 0:
                        result.append(next_char)
                        count[next_char] -= 1
                        next_char_found = True
                        break
                if not next_char_found:
                    break
        else:
            i += 1
    return ''.join(result)

print(repeatLimitedString("cczazcc", 3))  # Output: zzcccac

Java

import java.util.*;

public class Solution {
    public static String repeatLimitedString(String s, int repeatLimit) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        StringBuilder result = new StringBuilder();
        for (int i = 25; i >= 0;) {
            if (count[i] > 0) {
                int use = Math.min(repeatLimit, count[i]);
                for (int j = 0; j < use; j++) {
                    result.append((char) ('a' + i));
                }
                count[i] -= use;
                if (count[i] > 0) {
                    int k;
                    for (k = i - 1; k >= 0 && count[k] == 0; k--);
                    if (k < 0) break;
                    result.append((char) ('a' + k));
                    count[k]--;
                }
            } else {
                i--;
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(repeatLimitedString("cczazcc", 3)); // Output: zzcccac
    }
}

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string repeatLimitedString(string s, int repeatLimit) {
    vector<int> count(26, 0);
    for (char c : s) count[c - 'a']++;
    string result = "";
    for (int i = 25; i >= 0;) {
        if (count[i] > 0) {
            int use = min(repeatLimit, count[i]);
            result.append(use, 'a' + i);
            count[i] -= use;
            if (count[i] > 0) {
                int j;
                for (j = i - 1; j >= 0 && count[j] == 0; j--);
                if (j < 0) break;
                result.push_back('a' + j);
                count[j]--;
            }
        } else {
            i--;
        }
    }
    return result;
}

int main() {
    string s = "cczazcc";
    int repeatLimit = 3;
    cout << repeatLimitedString(s, repeatLimit) << endl;
    return 0;
}

JavaScript

function repeatLimitedString(s, repeatLimit) {
    const count = new Array(26).fill(0);
    for (const char of s) {
        count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    let result = '';
    for (let i = 25; i >= 0;) {
        if (count[i] > 0) {
            let use = Math.min(repeatLimit, count[i]);
            result += String.fromCharCode('a'.charCodeAt(0) + i).repeat(use);
            count[i] -= use;
            if (count[i] > 0) {
                let nextCharFound = false;
                for (let j = i - 1; j >= 0; j--) {
                    if (count[j] > 0) {
                        result += String.fromCharCode('a'.charCodeAt(0) + j);
                        count[j]--;
                        nextCharFound = true;
                        break;
                    }
                }
                if (!nextCharFound) break;
            }
        } else {
            i--;
        }
    }
    return result;
}

console.log(repeatLimitedString("cczazcc", 3)); // Output: zzcccac

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void sortDescending(char* s, int* count) {
    for (int i = 0; i < 26; i++) count[i] = 0;
    for (int i = 0; s[i]; i++) count[s[i] - 'a']++;
}

char * repeatLimitedString(char * s, int repeatLimit){
    char* result = (char *)malloc(sizeof(char) * (strlen(s) + 1));
    int idx = 0;
    int count[26];
    sortDescending(s, count);
    for (int i = 25; i >= 0; ) {
        if (count[i] > 0) {
            int use = count[i] > repeatLimit ? repeatLimit : count[i];
            for (int j = 0; j < use; j++) {
                result[idx++] = 'a' + i;
            }
            count[i] -= use;
            if (count[i] > 0) {
                int k;
                for (k = i - 1; k >= 0 && count[k] == 0; k--);
                if (k < 0) break;
                result[idx++] = 'a' + k;
                count[k]--;
            }
        } else {
            i--;
        }
    }
    result[idx] = '\0';
    return result;
}

int main() {
    char s[] = "cczazcc";
    int repeatLimit = 3;
    char *result = repeatLimitedString(s, repeatLimit);
    printf("%s\n", result);
    free(result);
    return 0;
}

using System;
using System.Text;

public class Solution {
    public static string RepeatLimitedString(string s, int repeatLimit) {
        int[] count = new int[26];
        foreach (char c in s) count[c - 'a']++;
        StringBuilder result = new StringBuilder();
        for (int i = 25; i >= 0;) {
            if (count[i] > 0) {
                int use = Math.Min(repeatLimit, count[i]);
                result.Append((char)('a' + i), use);
                count[i] -= use;
                if (count[i] > 0) {
                    int k;
                    for (k = i - 1; k >= 0 && count[k] == 0; k--);
                    if (k < 0) break;
                    result.Append((char)('a' + k));
                    count[k]--;
                }
            } else {
                i--;
            }
        }
        return result.ToString();
    }

    public static void Main() {
        Console.WriteLine(RepeatLimitedString("cczazcc", 3)); // Output: zzcccac
    }
}

The Python solution uses a Counter to track character frequencies and a sorted list to ensure char iteration is in descending order. It assembles the output string by using characters up to the repeat limit and switching to a smaller character if required.

Complexity

Time Complexity: O(n + m log m) due to sorting step
Space Complexity: O(m)

Try this approach in the editor

Approach 2: Greedy Algorithm

First, we use an array cnt of length 26 to count the number of occurrences of each character in string s. Then, we enumerate the ith letter of the alphabet in descending order, each time taking out at most min(cnt[i], repeatLimit) of letter i. If after taking them out cnt[i] is still greater than 0, we continue to take the jth letter of the alphabet, where j is the largest index satisfying j < i and cnt[j] > 0, until all letters are taken.

TypeScript

function repeatLimitedString(s: string, repeatLimit: number): string {
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        cnt[c.charCodeAt(0) - 97]++;
    }
    const ans: string[] = [];
    for (let i = 25, j = 24; ~i; --i) {
        j = Math.min(j, i - 1);
        while (true) {
            for (let k = Math.min(cnt[i], repeatLimit); k; --k) {
                ans.push(String.fromCharCode(97 + i));
                --cnt[i];
            }
            if (!cnt[i]) {
                break;
            }
            while (j >= 0 && !cnt[j]) {
                --j;
            }
            if (j < 0) {
                break;
            }
            ans.push(String.fromCharCode(97 + j));
            --cnt[j];
        }
    }
    return ans.join('');
}

func repeatLimitedString(s string, repeatLimit int) string {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	var ans []byte
	for i, j := 25, 24; i >= 0; i-- {
		j = min(j, i-1)
		for {
			for k := min(cnt[i], repeatLimit); k > 0; k-- {
				ans = append(ans, byte(i+'a'))
				cnt[i]--
			}
			if cnt[i] == 0 {
				break
			}
			for j >= 0 && cnt[j] == 0 {
				j--
			}
			if j < 0 {
				break
			}
			ans = append(ans, byte(j+'a'))
			cnt[j]--
		}
	}
	return string(ans)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Frequency Count	Time Complexity: O(n + m log m) due to sorting step Space Complexity: O(m)
Greedy Algorithm	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force with Re-Sorting	O(n² log n)	O(n)	Conceptual understanding of greedy character selection
Greedy with Max Heap	O(n log k)	O(k)	General solution when alphabet size or options are dynamic
Greedy with Frequency Count	O(n + 26)	O(26)	Optimal solution for lowercase letters with fixed alphabet

Frequently asked questions

Is Construct String With Repeat Limit easy or hard?

Construct String With Repeat Limit is rated Medium on LeetCode. The challenge lies in enforcing the repeat constraint while still producing the lexicographically largest result using a greedy strategy.

Construct String With Repeat Limit Python/Java solution

Most implementations use a greedy loop with a frequency array of size 26. Track the largest available character, append it up to repeatLimit times, and insert the next smaller character when needed to reset the repetition constraint. The same logic translates directly across Python, Java, C++, C#, and JavaScript.

How to solve Construct String With Repeat Limit in O(n)?

Count the frequency of each character and iterate from 'z' to 'a'. Append the largest character up to repeatLimit times. If more occurrences remain, insert the next smaller available character once before continuing. Since the alphabet is fixed, scanning for the next character is constant time, giving O(n + 26) overall complexity.

What is the best approach for Construct String With Repeat Limit?

The best approach is a greedy strategy using a frequency count of characters. Always place the largest available character up to the repeatLimit, and if more copies remain, insert the next largest character once to break the repetition. This produces the lexicographically largest valid string in O(n + 26) time and O(26) space.

Is Construct String With Repeat Limit asked at Google/Amazon/Meta?

Greedy string construction problems with constraints are common in interviews at companies like Amazon, Google, and Meta. Variations of this question test your ability to prioritize lexicographic order while enforcing repetition limits.

What data structure is used in Construct String With Repeat Limit?

Two common implementations exist: a max heap (priority queue) with frequency counts, or a fixed-size frequency array for the 26 lowercase letters. The array-based counting approach is more efficient and avoids heap operations.

What is the time complexity of Construct String With Repeat Limit?

The optimal greedy frequency-count solution runs in O(n + 26) time because each character from the string is processed once and the alphabet size is fixed. Space complexity is O(26) for storing character frequencies.

Construct String With Repeat Limit solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Frequency Count

Approach 2: Greedy Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Construct String With Repeat Limit solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Frequency Count

Approach 2: Greedy Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems