Formatted question description: https://leetcode.ca/all/2182.html

# 2182. Construct String With Repeat Limit (Medium)

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 = 3Output:"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 = 2Output:"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.

**Similar Questions**:

## Solution 1. Greedy + Counting

Store frequency of characters in `int cnt[26]`

.

We pick characters in batches. In each batch, we pick the first character from `z`

to `a`

whose `cnt`

is positive with the following caveats:

- If the current character is the same as the one used in the previous batch, we need to skip it.
- On top of case 1, if the
`cnt`

of the character used in the previous batch is positive, then we can only fill a single character in this batch.

```
// OJ: https://leetcode.com/problems/construct-string-with-repeat-limit/
// Time: O(N)
// Space: O(1)
class Solution {
public:
string repeatLimitedString(string s, int limit) {
int cnt[26] = {};
string ans;
for (char c : s) cnt[c - 'a']++;
while (true) {
int i = 25;
bool onlyOne = false;
for (; i >= 0; --i) {
if (ans.size() && i == ans.back() - 'a' && cnt[i]) { // the character of our last batch still has some count left, so we only insert a single character in this batch
onlyOne = true;
continue;
}
if (cnt[i]) break; // found a character with positive count, fill with this character
}
if (i == -1) break; // no more characters to fill, break;
int fill = onlyOne ? 1 : min(cnt[i], limit);
cnt[i] -= fill;
while (fill--) ans += 'a' + i;
}
return ans;
}
};
```

## Discuss

https://leetcode.com/problems/construct-string-with-repeat-limit/discuss/1784718

## Note

I saw some code with the following loops

```
for (int i = 1; i <= 100000; ++i) {
for (int j = i; j <= 100000; j += i) {
// Some O(1) operation
}
}
```

The time complexity of these loops is roughly `O(NlogN)`

. Because `1/1+1/2+...+1/N`

is roughly `logN`

. See https://math.stackexchange.com/questions/3367037/sum-of-1-1-2-1-3-1-n