What is the best way to approach the "Construct String With Repeat Limit" problem?

The best approach is to use a greedy strategy, starting with the lexicographically largest characters and ensuring the repeatLimit constraint is respected through a heap or hash table.

How do I handle characters that appear more than repeatLimit times?

When a character appears more than the allowed repeatLimit, adjust the number of repetitions or skip to the next valid character, ensuring the result remains valid.

What is the time complexity of this problem?

The time complexity is O(N * log K), where N is the length of the string and K is the number of unique characters in the string.

What makes the solution greedy?

The solution is greedy because it always picks the lexicographically largest available character while ensuring the repeatLimit constraint is met.

Can you explain the use of the heap in this problem?

The heap is used to efficiently select the largest character available for string construction. It ensures that at each step, we can quickly access the next valid character to append.

#2182

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

构造限制重复的字符串

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

哈希表字符串贪心堆（优先队列）计数

题目描述

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

lightbulb

解题思路

方法一：贪心

我们先用一个长度为 $26$ 的数组 $cnt$ 统计字符串 $s$ 中每个字符出现的次数，然后从大到小枚举字母表的第 $i$ 个字母，每次取出最多 $\min(cnt[i], repeatLimit)$ 个字母 $i$ ，如果取完后 $cnt[i]$ 还大于 $0$ ，则继续取字母表中第 $j$ 个字母，其中 $j$ 是最大的满足 $j < i$ 且 $cnt[j] > 0$ 的下标，直到取完所有字母。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - ord("a")] += 1
        ans = []
        j = 24
        for i in range(25, -1, -1):
            j = min(i - 1, j)
            while 1:
                x = min(repeatLimit, cnt[i])
                cnt[i] -= x
                ans.append(ascii_lowercase[i] * x)
                if cnt[i] == 0:
                    break
                while j >= 0 and cnt[j] == 0:
                    j -= 1
                if j < 0:
                    break
                cnt[j] -= 1
                ans.append(ascii_lowercase[j])
        return "".join(ans)

speed

复杂度分析

指标	值
时间	O(N \cdot \log K)
空间	O(K)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain how a greedy approach ensures the largest lexicographical string while respecting the repeatLimit?
question_mark
Does the candidate recognize the importance of using a max heap for efficient character selection?
question_mark
Is the candidate able to demonstrate an understanding of the trade-offs between greedy strategies and maintaining constraints?

warning

常见陷阱

外企场景

error
Forgetting to handle the repeatLimit constraint when appending characters, leading to invalid strings.
error
Overcomplicating the problem by not using the heap or hash table efficiently for character management.
error
Misunderstanding the lexicographical order, leading to suboptimal solutions where smaller characters are selected first.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the repeatLimit was higher than the length of the string? How would the solution change?
arrow_right_alt
How does this solution handle edge cases like an empty string or a string where all characters are the same?
arrow_right_alt
What if the characters in the string are already sorted? How would that impact the approach?

help

常见问题

外企场景

继续练习

#3081 替换字符串中的问号使分数最小 #2131 连接两字母单词得到的最长回文串 #2384 最大回文数字