LeetCode：1405.最长快乐字符串————中等

题目

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 <= 100
• a + b + c > 0

解题思路

• 贪心策略。
• 我们需要把字符数量最多的最先进行添加。按字符数量分为low， mid，high，我们优先使用high，但是需要满足一些条件：①：ans的字符小于2或ans的字符超过2并且最后两个字符不全是high。②：high的字符数量至少为1。

Code

class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
dic = {'a': a, 'b': b, 'c': c }
ans = ''
while True:
low, mid, high = sorted(dic.keys(), key=lambda x: dic[x])
if (len(ans) <2 or not ans[-1] == ans[-2] == high) and dic[high]:
ans += high
dic[high] -= 1
elif dic[mid]:
ans += mid
dic[mid] -= 1
else:
break
return ans


运行结果