算法刷题——构造限制重复的字符串（力扣）

题目描述

传送门
构造限制重复的字符串：给你一个字符串 s 和一个整数repeatLimit ，用 s 中的字符构造一个新字符串repeatLimitedString ，使任何字母 连续 出现的次数都不超过repeatLimit 次。你不必使用 s 中的全部字符。
返回字典序最大的repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。

示例 1：
输入：s = “cczazcc”, repeatLimit = 3
输出：“zzcccac”
解释：使用 s 中的所有字符来构造 repeatLimitedString “zzcccac”。
字母 ‘a’ 连续出现至多 1 次。
字母 ‘c’ 连续出现至多 3 次。
字母 ‘z’ 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 “zzcccac” 。
注意，尽管 “zzcccca” 字典序更大，但字母 ‘c’ 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。

示例 2：
输入：s = “aababab”, repeatLimit = 2
输出：“bbabaa”
解释：
使用 s 中的一些字符来构造 repeatLimitedString “bbabaa”。
字母 ‘a’ 连续出现至多 2 次。
字母 ‘b’ 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 “bbabaa” 。
注意，尽管 “bbabaaa” 字典序更大，但字母 ‘a’ 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。

提示：

• 1 <= repeatLimit <= s.length <= 10⁵
• s 由小写英文字母组成

我的解法

// 没有解出来

思路

因为题目是要返回字典序最大的repeatLimitedString，所以一开始我想通过两个优先队列（堆）priority_queue<pair<char,int>> hp，其中pair<char,int>中char为字符串中出现过的字符，int为字符串出现的次数，一个堆的堆顶为最大的字符，另一个堆的堆顶为次大的字符，从而实现最大的repeatLimitedString的输出，但是思绪太乱，没有理清楚解决问题的先后顺序，因此最后并没有解答出本题。

结果

无

官方题解

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        int N = 26;
        vector<int> count(N);
        // 记录字符串中各个字符出现的次数
        for(auto c:s){
            count[c - 'a']++;
        }

        string res;
        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]--;
                res.push_back('a' + i);
                m++;
            }
            else if(j >= i || count[j] == 0){// 查找次大可填入的字符
                j--;
            }
            else{// 当前字符已经超过限制，填入次大字符，并且重置 m
                count[j]--;
                res.push_back('a' + j);
                m = 0;
            }
        }
        return res;
    }
};

分析

思路：通过贪心算法和双指针实现了最大repeatLimitedString的输出。
时间复杂度：
O(n+Σ)，其中 n 为 s 的长度，Σ=26为字符集的大小。

空间复杂度：
O(Σ) 或 O(n+Σ)。返回值不计入空间复杂度。某些语言字符串生成过程中需要 O(n)的空间开销。

查漏补缺

对于一个问题的解决，一定要理清思路，第一步做什么，第二步做什么……这样才能把问题清晰地解决。
就好像本题：
第一步：判断最大字符是否还有，如果没有了，就需要更新最大字符的位置和可重复次数；
第二步：最大字符还有并且重复次数还没超出限制，就往结果中添加最大字符，并更新重复次数；
第三步：如果重复次数超出限制，就需要添加次大字符，在添加前，首先要寻找次大字符并且判断次大字符是否还有，如果没有了就需要寻找到还存在的次大字符；
第四步：添加次大字符，添加后还需要跟新其还剩余的数量。

更新日期

2024.1.13
欢迎前来讨论指正。

参考来源

力扣链接