[leetcode] 1405. Longest Happy String

[leetcode] 1405. Longest Happy String

Description

A string is called happy if it does not have any of the strings ‘aaa’, ‘bbb’ or ‘ccc’ as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

s is happy and longest possible.s contains at most a occurrences of the letter ‘a’, at most b occurrences of the letter ‘b’ and at most c occurrences of the letter ‘c’.s will only contain ‘a’, ‘b’ and ‘c’ letters.

If there is no such string s return the empty string “”.

Example 1:

Input: a = 1, b = 1, c = 7Output: "ccaccbcc"Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0Output: "aabaa"Explanation: It's the only correct answer in this case.

Constraints:

0 <= a, b, c <= 100a + b + c > 0

分析

题目的意思是：给定a,b,c的数量，构造一个最长的happy字符串，其中a,b,c不能出现连续3次。

这道题要用贪心的算法，从数量多的字符开刀来拼接最终的字符串，所以需要排序。但是选出来以后不能直接拼接到res后面，要看res里面最后两个字符是否和现在所选的字符相等（不能连续出现3次），如果不能才能拼接；否则遍历找到满足条件的字符拼接为止。

代码

class Solution: def longestDiverseString(self, a: int, b: int, c: int) -> str: x=[[a,'a'],[b,'b'],[c,'c']] res='' while(True): for num in sorted(x,reverse=True): if(num[0]<=0): return res if(len(res)>1 and res[-2:]==num[1]*2): continue res+=num[1] num[0]-=1 break return res

参考文献

​​[LeetCode] python 贪心​​​​2020 第15周 LeetCode 记录​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。