1405. 最长快乐字符串 #
链接 #
题目 #
如果字符串中不含有任何 '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
解答 #
举个例子 ：a = 1, b = 1, c = 7
1、取数量最多的字母 c，每两个组成一个字符串，得到：['cc','cc','cc','c']
2、把剩余字母 a 逐个拼接到每个字符串末尾，得到：['cca','cc','cc','c']，此时一轮循环尚未结束
3、一轮循环没结束，字母 a 已耗尽，继续该轮循环，把剩余字母 b 逐个拼接到每个字符串末尾，得到：['cca','ccb','cc','c']
4、拼接所有字符串再处理末尾多余字符，得到：‘ccaccbcc’
作者：解码 链接：https://leetcode.cn/problems/longest-happy-string/solutions/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
# 创建一个最大堆
max_heap = []
# 如果字符数量大于0，则加入堆中，使用负数是因为Python的heapq实现的是最小堆
if a > 0:
heapq.heappush(max_heap, (-a, 'a'))
if b > 0:
heapq.heappush(max_heap, (-b, 'b'))
if c > 0:
heapq.heappush(max_heap, (-c, 'c'))
res = []
while max_heap:
count, char = heapq.heappop(max_heap) # 取出当前数量最多的字符
# 检查是否会形成 aaa, bbb, ccc
if len(res) >= 2 and res[-1] == res[-2] == char:
if not max_heap:
break # 如果没有其他字符可以使用，则结束
count_next, char_next = heapq.heappop(max_heap) # 取出下一个数量最多的字符
res.append(char_next)
count_next += 1 # 更新数量
if count_next < 0: # 如果还有剩余，则放回堆中
heapq.heappush(max_heap, (count_next, char_next))
heapq.heappush(max_heap, (count, char)) # 将当前字符放回堆中，以便下一轮使用
else:
res.append(char)
count += 1 # 更新数量
if count < 0: # 如果还有剩余，则放回堆中
heapq.heappush(max_heap, (count, char))
return ''.join(res)
为什么贪心策略能够有效？ #
关键在于 没有后效性：在这个问题中，每次选择字符时，我们只需要考虑当前的状态，而不需要考虑之前的决策过程。这意味着每次选择都是独立的，不会因为之前的选择而变得不可行。