LeetCode 2182. 构造限制重复的字符串，贪心模拟，把控细节

一、题目

1、题目描述

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

返回?字典序最大的?repeatLimitedString?。

如果在字符串?a?和?b?不同的第一个位置，字符串?a?中的字母在字母表中出现时间比字符串?b?对应的字母晚，则认为字符串?a?比字符串?b?字典序更大?。如果字符串中前?min(a.length, b.length)?个字符都相同，那么较长的字符串字典序更大。

2、接口描述

?

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        
    }
};

3、原题链接

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

二、解题报告

1、思路分析

统计各个字符的个数，从当前最大的字符开始放，如果个数大于限制，就先放repeatLimit个，然后放一个次小的，然后接着放最大的，如果找不到次小的就退出循环

2、复杂度

时间复杂度：O(nU) 空间复杂度：O(U)，n为字符串长度，U为字符集大小

3、代码详解

?

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        int cnt[26]{0};
        for(auto x : s)
            cnt[x - 'a']++;
        string ret;
        for(int i = 25 ; i >= 0 ; i--)
        {
            if(!cnt[i]) continue;
            int j = i;
            while(j >= 0 && cnt[i] > repeatLimit)
            {
                ret.append(repeatLimit , i + 'a') , cnt[i] -= repeatLimit;
                for(j = i - 1 ; j >= 0 && !cnt[j] ; j--);
                if(j < 0) break;
                ret.push_back(j + 'a') , cnt[j]--;
            }
            if(j < 0) break;
            ret.append(cnt[i] <= repeatLimit ? cnt[i] : repeatLimit , i + 'a') , cnt[i] = 0;
            
        }
        return ret;
    }
};