2024.1.13力扣每日一题——构造限制重复的字符串

2024.1.13

- - 题目来源
  - 我的题解
  - - 方法一计数+模拟

题目来源

力扣每日一题；题序：2182

我的题解

方法一计数+模拟

因为字符串s由小写字母构成，因此使用一个int[26]的数组保存每个字符的数量，然后从最大的字符开始构造结果字符串sb，基于贪心策略，如果当前剩下的最大字符cur的数量大于repeatLimit，则直接添加repeatLimit个cur到sb中，并且计数-repeatLimit，这时要使最终的sb字典序最大，则需要加入除cur外的字符中最大的字符，只需要加1个就行，作用是为了防止cur连续个数>repeatLimit。最终通过模拟构造除结果字符串sb

时间复杂度：O(|S|*n)。|S|表示26个字符，n表示字符串s的长度
空间复杂度：O(|S|)

 public String repeatLimitedString(String s, int repeatLimit) {
    int[] ch=new int[26];
    //计数
    for(int i=0;i<s.length();i++){
        char c=s.charAt(i);
        ch[c-'a']++;
    } 
    StringBuilder sb=new StringBuilder();
    //模拟
    for(int i=25;i>=0;i--){
        int index=i-1;//下一个最大字符
        boolean f=false;//是添加下一个最大字符还是当前字符
        while(index>=-1&&ch[i]>0){
            if(!f){
            	//当前最大字符的数量大于等于repeatLimit，直接在结果集中加入repeatLimit个当前最大字符
                if(ch[i]>repeatLimit){
                    ch[i]-=repeatLimit;
                    sb.append(createS((char)('a'+i),repeatLimit));
                }else{//当前最大字符的数量小于repeatLimit，直接在结果集中加入ch[i]个当前最大字符,当前最大字符清零
                    sb.append(createS((char)('a'+i),ch[i]));
                    ch[i]=0;
                }
                f=!f;
            }else{
            	//找到比当前字符小的最大字符
                while(index>=0&&ch[index]<=0){
                    index--;
                }
                // 能找到，则加入一个比当前字符小的最大字符
                if(index>=0){
                    sb.append((char)('a'+index));
                    ch[index]-=1;
                }else{//找不到，结束循环
                    break;
                }
                f=!f;
            }
        }
    }
    return sb.toString();
}
// 添加count个字符ch
public StringBuilder createS(char ch,int count){
    StringBuilder sb=new StringBuilder();
    for(int i=0;i<count;i++){
        sb.append(ch);
    }
    return sb;
}

更优雅的官方题解

static public int N = 26;
public String repeatLimitedString(String s, int repeatLimit) {
    int[] count = new int[N];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
    }
    StringBuilder ret = new StringBuilder();
    int m = 0;
    for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
        if (count[i] == 0) { // 当前字符已经填完，填入后面的字符，重置 m
            m = 0;
            i--;
        } else if (m < repeatLimit) { // 当前字符未超过限制
            count[i]--;
            ret.append((char)('a' + i));
            m++;
        } else if (j >= i || count[j] == 0) { // 当前字符已经超过限制，查找可填入的其他字符
            j--;
        } else { // 当前字符已经超过限制，填入其他字符，并且重置 m
            count[j]--;
            ret.append((char)('a' + j));
            m = 0;
        }
    }
    return ret.toString();
}