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 = 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 <= 105
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