【Leetcode】2182. 构造限制重复的字符串

题目

2182. 构造限制重复的字符串

问题：给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。

示例 1：
输入：s = “cczazcc”, repeatLimit = 3
输出：“zzcccac”
解释：
使用 s 中的所有字符来构造 repeatLimitedString “zzcccac”。
字母 ‘a’ 连续出现至多 1 次。
字母 ‘c’ 连续出现至多 3 次。
字母 ‘z’ 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 “zzcccac” 。
注意，尽管 “zzcccca” 字典序更大，但字母 ‘c’ 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。
返回 字典序最大的 repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。

示例 2：
输入：s = “aababab”, repeatLimit = 2
输出：“bbabaa”
解释：
使用 s 中的一些字符来构造 repeatLimitedString “bbabaa”。
字母 ‘a’ 连续出现至多 2 次。
字母 ‘b’ 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 “bbabaa” 。
注意，尽管 “bbabaaa” 字典序更大，但字母 ‘a’ 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。

思路

这道题是一个简单的构造题，简单来说就是用题目给i出的字符串重新构造一个字典序最大的字符串。
记录所有字母的出现次数，然后我们从大的字母开始枚举。如果当前字母没用完就全加到答案中，否则就向前一个小的字母借一个，如果已经没有更加小的字符了则退出。

代码

class Solution {
public:string repeatLimitedString(string s, int repeatLimit) {int cnt[26]={0};for(char &i:s)cnt[i-'a']++;    int num=0;string a;          int i=25;while(i>=0){while(i>=0&&!cnt[i]){i--;num=0;}if(i<0)break;if(num<repeatLimit){a+=(char)(i+'a');    cnt[i]--;        num++;}else{int j=i-1;if(j<0)break;while(j>=0&&!cnt[j]){j--;}if(j<0)break;else{a+=(char)(j+'a');cnt[j]--;num=0;                    }}}return a;}
};