力扣2182、构造限制重复的字符串

题目

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

返回 字典序最大的 repeatLimitedString 。

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

思路

• 遍历整个字符串，统计各个字符出现的次数，最后倒序遍历字符串
• 动态减少 最大的字符的数量 和 第二大的字符的数量
• 如果最大的字符的数量 大于 repeatLimit，那么我们加一个第二大字符

题解

c++版本

class Solution {
public:
    int vis[26] = {0};
    
    string repeatLimitedString(const string s, const int repeatLimit) {
        int n = s.size();
        if (n == 0) return "";
        for (int i = 0; i < n; ++i) {
            ++vis[s[i] - 'a'];
        }
        int t, r = 25;
        string ret = "";
        while (n) {
            
            while (r >= 0 && vis[r] == 0) --r;
            t = repeatLimit;
            
            if (vis[r] > t) {
                for (int i = 0; i < t; ++i) ret += r + 'a';
                vis[r] -= t;
                n -= t;
                if (r == 0) break;

                int l = r - 1; //寻找第二大字符
                while (l >= 0 && vis[l] == 0) --l;
                if (l < 0 || vis[l] == 0) break; //没有第二大字符了，直接退出循环，否则最后加进去的都是最大字符，导致连续字符大于repeatLimit
                --vis[l];
                --n;
                ret += l + 'a';
                
            } else { // <=
                for (int i = 0; i < vis[r]; ++i, --n) {
                    ret += r + 'a';
                }
                vis[r] = 0;
            }
            //cout << ret << endl;
        }
        return ret;
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-string-with-repeat-limit