1405. 最长快乐字符串（Rating 1820）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1405. 最长快乐字符串

Rating 1820

思路

简化一下，先考虑单个字母排列且相邻字母不同的情况，如

cabca

如果还有多余字母，再相同字母的位置上加。比如还有2个c，那么

ccabcca

对于简化的情况，贪心即可，保证相邻字母不同的情况下先排数量多的。

代码

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        cnt = {'a' : a, 'b' : b, 'c' : c} # 维护每个字母的数量
        last = ' ' # 维护上一个字母
        ret = []
        while True:
            lst = [(cnt['a'], 'a'), (cnt['b'], 'b'), (cnt['c'], 'c')]
            lst.sort() # 排序
            mx_num, mx_c = lst[2] # 最大值和字母
            md_num, md_c = lst[1] # 中间值和字母
            mn_num, mn_c = lst[0] # 最小值和字母
            if mx_c == last: # 最大值和上一个字母相同
                if md_num > 0: # 用中间值，需要中间值 > 0
                    ret.append(md_c)
                    md_num -= 1
                else: # 中间值 == 0，说明字母都用完了
                    break
            else: # 最大值和上一个字母不同
                if mx_num > 0: # 用最大值，需要最大值 > 0
                    ret.append(mx_c)
                    mx_num -= 1
                else: # 最大值 == 0，说明字母都用完了
                    break
            last = ret[-1] # 更新上一个字母
            cnt[mx_c] = mx_num # 更新每个字母的数量
            cnt[md_c] = md_num # 更新每个字母的数量
            cnt[mn_c] = mn_num # 更新每个字母的数量
        s = ''
        for idx, c in enumerate(ret):
            if cnt[c] > 0: # 对于每个位置的字母，如果还有剩余，则可以填充2个
                s += c * 2
                cnt[c] -= 1
            else: # 没有剩余，填充1个即可
                s += c
        return s