思路
首先统计每个字符的个数,然后从后向前按照题意添加字符
解题方法
从后向前添加字符:1.当前字符个数<=repeatLimit,直接添加
2.当前字符个数>repeatLimit,添加repeatLimit个,然后插入一个下一级字符
时间复杂度:O(n²)
空间复杂度:O(n)
Code
class Solution {
public String repeatLimitedString(String s, int repeatLimit) {
int[] cnt = new int[26];
for(int i=0;i<s.length();i++){ //使用数组统计每次字符个数
char c = s.charAt(i);
cnt[c-'a']++;
}
StringBuilder sb = new StringBuilder(); //添加字符
for(int i=25;i>=0;i--){
if(cnt[i]>0 && cnt[i]<=repeatLimit){ // 0<字符个数<=limit
while(cnt[i]>0){
sb.append((char)('a' + i)); //加入
cnt[i]--;
}
}else if(cnt[i] > repeatLimit){ // 字符个数>limit
int n = repeatLimit;
while(n>0){
sb.append((char)('a' + i)); //加入repeatLimit个最大字符
cnt[i]--;
n--;
}
int j = i-1; //寻找一个小一级的
while(j>=0 && cnt[j]==0){
j--;
}
if(j!=-1){
sb.append((char)('a' + j)); //找到了
cnt[j]--;
i++; //重新插入上一个剩余的字母
}else{ //没找到
return sb.toString();
}
}//if--elseif
}
return sb.toString();
}
}
注:依旧是参考答案的一天。。。。。。