LeetCode 题解工作台
最长快乐字符串
如果字符串中不含有任何 'aaa' ， 'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。 给你三个整数 a ， b ， c ，请你返回 任意一个 满足下列全部条件的字符串 s ： s 是一个尽可能长的快乐字符串。 s 中 最多 有 a 个字母 'a' 、 b 个…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
贪心，优先选择剩余最多的字符，通过优先队列或排序，确保每次选到的字符都是剩余最多的（为了避免出现连续 3 个一样的字符，一些情况需要选择剩余第二多的字符）。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
s是一个尽可能长的快乐字符串。s中 最多 有a个字母'a'、b个字母'b'、c个字母'c'。s中只含有'a'、'b'、'c'三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 ""。
示例 1：
输入：a = 1, b = 1, c = 7 输出："ccaccbcc" 解释："ccbccacc" 也是一种正确答案。
示例 2：
输入：a = 2, b = 2, c = 1 输出："aabbc"
示例 3：
输入：a = 7, b = 1, c = 0 输出："aabaa" 解释：这是该测试用例的唯一正确答案。
提示：
0 <= a, b, c <= 100a + b + c > 0
解题思路
方法一：贪心 + 优先队列
贪心，优先选择剩余最多的字符，通过优先队列或排序，确保每次选到的字符都是剩余最多的（为了避免出现连续 3 个一样的字符，一些情况需要选择剩余第二多的字符）。
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
h = []
if a > 0:
heappush(h, [-a, 'a'])
if b > 0:
heappush(h, [-b, 'b'])
if c > 0:
heappush(h, [-c, 'c'])
ans = []
while len(h) > 0:
cur = heappop(h)
if len(ans) >= 2 and ans[-1] == cur[1] and ans[-2] == cur[1]:
if len(h) == 0:
break
nxt = heappop(h)
ans.append(nxt[1])
if -nxt[0] > 1:
nxt[0] += 1
heappush(h, nxt)
heappush(h, cur)
else:
ans.append(cur[1])
if -cur[0] > 1:
cur[0] += 1
heappush(h, cur)
return ''.join(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(a + b + c) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate chooses the correct greedy strategy to handle character selection efficiently.
- question_mark
They successfully implement a heap to manage character frequencies, optimizing selection.
- question_mark
The candidate handles edge cases such as imbalances in character counts correctly, ensuring a valid string.
常见陷阱
外企场景- error
Not managing the heap correctly, leading to inefficient or incorrect character selection.
- error
Failing to check the validity of the string after each character is added, possibly leading to two consecutive characters.
- error
Not handling edge cases where one character's count is too large to form a valid string, resulting in an empty string return.
进阶变体
外企场景- arrow_right_alt
Modify the problem to use more than three characters and still construct the longest happy string.
- arrow_right_alt
Change the problem to allow two consecutive identical characters but with a maximum count.
- arrow_right_alt
Implement the problem where the goal is to minimize the length of the string instead of maximizing it.