https://leetcode.com/problems/longest-happy-string
1405. Longest Happy String
一个字串 s 是 快乐的条件如下
s 只包含 'a', 'b', 'c'
s 不包含 'aaa', 'bbb', 'ccc'
s 分别最多只有 a, b, c 个 'a', 'b', 'c'
给3个数a,b,c 回传最长的快乐字串
如果有多种可能 回传其中一种 如果没有 则回传空字串
Example 1:
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" 也是一种正确答案
Example 2:
Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: 这是这题的唯一解
Constraints:
0 <= a, b, c <= 100
a + b + c > 0
思路：
每种字母最多连续2次 用一个字典记录当下各个字母使用的次数
不过实际只会有 1,0,0 或 2,0,0 两种 因为决定要加哪个字母后 另外两个都会归0
字母与剩余次数则做成列表 每次进行排序
当最多的字母已使用2次 则换为第二多的 如果第二多的剩0次 则直接回传答案
Python Code:
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
ans = ''
items = [[a, 'a'], [b, 'b'], [c, 'c']]
counts = {'a': 0, 'b': 0, 'c': 0}
for _ in range(a+b+c):
items.sort(reverse=True)
first, second, third = items
if not ans:
ans += first[1]
first[0] -= 1
counts[first[1]] += 1
continue
if counts[first[1]] == 2:
if second[0] > 0:
ans += second[1]
second[0] -= 1
counts[second[1]] += 1
counts[first[1]] = 0
counts[third[1]] = 0
else:
return ans
else:
ans += first[1]
counts[first[1]] += 1
first[0] -= 1
counts[second[1]] = 0
counts[third[1]] = 0
return ans
好丑 :(
话说这个月又累计3次没答题了 好耶 再一次就8888