|
…
|
||
|---|---|---|
| .. | ||
| README.md | ||
| README_EN.md | ||
| Solution.cpp | ||
| Solution.go | ||
| Solution.java | ||
| Solution.py | ||
| Solution.ts | ||
README_EN.md
| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
| true | Medium | https://github.com/doocs/leetcode/edit/main/solution/2100-2199/2182.Construct%20String%20With%20Repeat%20Limit/README_EN.md | 1680 | Weekly Contest 281 Q3 |
|
2182. Construct String With Repeat Limit
Description
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 <= 105sconsists of lowercase English letters.
Solutions
Solution 1: 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 i$th 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 j$th letter of the alphabet, where $j is the largest index satisfying j < i and cnt[j] > 0, until all letters are taken.
The time complexity is O(n + |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of string s, and \Sigma is the character set. In this problem, |\Sigma| = 26.
Python3
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
cnt = [0] * 26
for c in s:
cnt[ord(c) - ord("a")] += 1
ans = []
j = 24
for i in range(25, -1, -1):
j = min(i - 1, j)
while 1:
x = min(repeatLimit, cnt[i])
cnt[i] -= x
ans.append(ascii_lowercase[i] * x)
if cnt[i] == 0:
break
while j >= 0 and cnt[j] == 0:
j -= 1
if j < 0:
break
cnt[j] -= 1
ans.append(ascii_lowercase[j])
return "".join(ans)
Java
class Solution {
public String repeatLimitedString(String s, int repeatLimit) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); ++i) {
++cnt[s.charAt(i) - 'a'];
}
StringBuilder ans = new StringBuilder();
for (int i = 25, j = 24; i >= 0; --i) {
j = Math.min(j, i - 1);
while (true) {
for (int k = Math.min(cnt[i], repeatLimit); k > 0; --k) {
ans.append((char) ('a' + i));
--cnt[i];
}
if (cnt[i] == 0) {
break;
}
while (j >= 0 && cnt[j] == 0) {
--j;
}
if (j < 0) {
break;
}
ans.append((char) ('a' + j));
--cnt[j];
}
}
return ans.toString();
}
}
C++
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
int cnt[26]{};
for (char& c : s) {
++cnt[c - 'a'];
}
string ans;
for (int i = 25, j = 24; ~i; --i) {
j = min(j, i - 1);
while (1) {
for (int k = min(cnt[i], repeatLimit); k; --k) {
ans += 'a' + i;
--cnt[i];
}
if (cnt[i] == 0) {
break;
}
while (j >= 0 && cnt[j] == 0) {
--j;
}
if (j < 0) {
break;
}
ans += 'a' + j;
--cnt[j];
}
}
return ans;
}
};
Go
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)
}
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('');
}