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