构造限制重复的字符串

难度: Medium

给你一个字符串 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 由小写英文字母组成

Submission

运行时间: 87 ms

内存: 17.0 MB

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        cnt = Counter(s)
        sl = sorted(cnt,reverse=True)
        f,s = 0,1
        res = ''
        while True:
            if f == len(sl):
                break
            fc = sl[f]
            if s >= len(sl):
                res += fc * min(repeatLimit, cnt[fc] )
                break 
            sc = sl[s]
            if cnt[fc] > cnt[sc] * repeatLimit:
                res += (fc * repeatLimit + sc) * cnt[sc]
                cnt[fc] -= repeatLimit * cnt[ sc]
                s = s + 1
            elif cnt[fc]  < cnt[sc] * repeatLimit:
                res += (fc * repeatLimit + sc) * ( (cnt[fc]-1) // repeatLimit ) + fc * (cnt[fc] - (cnt[fc]-1) // repeatLimit * repeatLimit)
                cnt[sc] -= (cnt[fc]-1) // repeatLimit
                f = s
                s = f + 1
            else:
                res += (fc * repeatLimit + sc) * cnt[sc]
                f = s + 1
                s = f + 1
            # print(res,f,s,cnt)
        return res

Explain

此题解采用排序和贪心策略构建字典序最大的字符串。首先，使用计数器统计字符串s中每个字符的出现次数。然后，对字符进行降序排序。通过迭代排序后的字符列表，贪心地构建结果字符串。每次尝试添加最大字母直到达到其限制repeatLimit，如果剩余数量仍较多，则尝试插入次大字母一次，以打破重复序列，再继续添加最大字母。此过程循环进行，直到无法添加更多字符为止。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        cnt = Counter(s)  # 计数s中每个字符的出现次数
        sl = sorted(cnt, reverse=True)  # 按字典序降序排列字符
        f, s = 0, 1  # 初始化指针f和s
        res = ''  # 初始化结果字符串
        while True:
            if f == len(sl):
                break  # 如果f指针遍历完成，则退出循环
            fc = sl[f]  # 最大的字符
            if s >= len(sl):
                res += fc * min(repeatLimit, cnt[fc])
                break  # 只剩一个字符，添加其最大可能重复数
            sc = sl[s]  # 次大的字符
            if cnt[fc] > cnt[sc] * repeatLimit:
                res += (fc * repeatLimit + sc) * cnt[sc]
                cnt[fc] -= repeatLimit * cnt[sc]
                s = s + 1
            elif cnt[fc] < cnt[sc] * repeatLimit:
                res += (fc * repeatLimit + sc) * ((cnt[fc] - 1) // repeatLimit) + fc * (cnt[fc] - (cnt[fc] - 1) // repeatLimit * repeatLimit)
                cnt[sc] -= (cnt[fc] - 1) // repeatLimit
                f = s
                s = f + 1
            else:
                res += (fc * repeatLimit + sc) * cnt[sc]
                f = s + 1
                s = f + 1
        return res

Explore

在构造字典序最大的字符串时，优先使用字典序最大的字符可以确保结果字符串尽可能大。贪心策略的核心是每一步都做出在当前看来最优的选择，这里的最优即为尽可能地使用字典序最大的字符。repeatLimit的限制确保了在保持字符最大化的同时，也不会超过字符的重复使用限制，从而平衡了结果字符串的构成。

当只剩一个字符时，选择添加该字符的最大可能重复数是因为没有其他字符可以选择用来打破重复或增加字符串长度。此时，使用剩余的单一字符到其最大重复限制是唯一可行的选择，以确保字符串尽可能长且符合repeatLimit的要求。

当f指针的字符数量远大于s指针的字符数量乘以repeatLimit时，如果只使用f指针的字符，很快就会达到该字符的重复限制。为了最大化使用f指针的字符同时避免违反repeatLimit，通过插入s指针的字符来打破可能的重复序列。这种方式可以有效利用字符库存，同时保持字符串的字典序尽可能大。

当fc的数量小于sc的数量乘以repeatLimit时，表示fc字符不足以填满可能的插入点。代码中，这种情况通过先尽可能地重复使用fc字符直到达到其repeatLimit，然后使用sc字符。计算fc能重复使用的次数，然后剩余的fc字符数量按照其实际数量添加。这样的处理方式保证了即使在字符数量有限的情况下，也能尽量构建出字典序最大的字符串。