【每日一题】构造限制重复的字符串-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】构造限制重复的字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

【贪心】【字符串】【2024-01-13】

题目来源

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

【每日一题】构造限制重复的字符串,LeetCode每日一题,贪心,字符串,2024-01-13

解题思路

方法一：贪心

思路

解题思想比较简单，利用贪心思想，每次选择当前剩余字符串中字典序最大的字符加到答案字符串末尾，如果答案字符串末尾的字符已经连续出现了 repeatLimit 次，则将字典序次大的字符加到答案字符串，随后继续选择当前剩余字符串的字典序最大的字符加到字符串末尾，直至使用完字符或没有新的字符可以合法加入。

想法比较简单，但实现起来稍微有点难度，具体实现见下方算法部分。

算法

const int N = 26;
class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        vector<int> count(N);
        // 统计每个字符出现次数
        for (char c : s) {
            count[c - 'a']++;
        }
        string ret;
        int m = 0;
        for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
            // 当前字符已经填完，填入后面的字符，重置 m
            if (count[i] == 0) { 
                m = 0;
                i--;  
            } 
            // 当前字符未超过限制
            else if (m < repeatLimit) { 
                count[i]--;
                ret.push_back('a' + i);
                m++;
            } 
            // 当前字符已经超过限制，查找可填入的其他字符
            else if (j >= i || count[j] == 0) { 
                j--;
            } 
            // 当前字符已经超过限制，填入其他字符，并且重置 m
            else { 
                count[j]--;
                ret.push_back('a' + j);
                m = 0;
            }
        }
        return ret;
    }
};

复杂度分析

时间复杂度： $\sum)$ ， $n$ 为字符串 s 的长度， $\sum = 26$ 为小写字符集的长度。