当前位置：首页 > news >正文

day-08 构造限制重复的字符串

news 2025/8/4 9:35:31

在这里插入图片描述
思路
首先统计每个字符的个数，然后从后向前按照题意添加字符

解题方法
从后向前添加字符：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<字符个数<=limitwhile(cnt[i]>0){sb.append((char)('a' + i));     //加入cnt[i]--;}}else if(cnt[i] > repeatLimit){               // 字符个数>limitint 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();}
}