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

思路
首先统计每个字符的个数，然后从后向前按照题意添加字符

解题方法
从后向前添加字符：1.当前字符个数<=repeatLimit,直接添加
2.当前字符个数>repeatLimit,添加repeatLimit个，然后插入一个下一级字符

时间复杂度:O(n2)

空间复杂度: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();

    }
}

注：依旧是参考答案的一天。。。。。。