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 = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.
Example 2:
Input: a = 2, b = 2, c = 1
Output: "aabbc"
Example 3:
Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.
Constraints:
0 <= a, b, c <= 100
a + b + c > 0
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        # 更新初始存量，根据插空规则修正单个字符最大可能的数量
        d = {'a':min(a,2*(b+c+1)),'b':min(b,2*(a+c+1)),'c':min(c,2*(b+a+1))}
        # 修正后的数量确保可以全部用在结果中，求和计算字符串总长
        n = sum(d.values())
        # 维护结果列表
        res = []
        # 单次插入一个字符，根据长度循环
        for _ in range(n):
            # 候选的字母
            cand = set(['a','b','c'])
            # 如果列表最后两个字符相同，根据规则不能插入连续三个，故将该字符从候选中删除
            if len(res)>1 and res[-1]==res[-2]:
                cand.remove(res[-1])
            # 贪心，在候选中选择存量最大的字符
            tmp = max(cand,key=lambda x:d[x])
            # 将它加到结果里
            res.append(tmp)
            # 把它的剩余计数减去1. 开始下一轮
            d[tmp] -= 1
        return ''.join(res)


class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        # 更新初始存量，根据插空规则修正单个字符最大可能的数量
        d = {'a':min(a,2*(b+c+1)),'b':min(b,2*(a+c+1)),'c':min(c,2*(b+a+1))}
        # 修正后的数量确保可以全部用在结果中，求和计算字符串总长
        n = sum(d.values())
        # 维护结果列表
        res = []
        # 单次插入一个字符，根据长度循环
        for _ in range(n):
            # 候选的字母
            cand = set(['a','b','c'])
            # 如果列表最后两个字符相同，根据规则不能插入连续三个，故将该字符从候选中删除
            if len(res)>1 and res[-1]==res[-2]:
                cand.remove(res[-1])
            # 贪心，在候选中选择存量最大的字符
            tmp = max(cand,key=lambda x:d[x])
            # 将它加到结果里
            res.append(tmp)
            # 把它的剩余计数减去1. 开始下一轮
            d[tmp] -= 1
        return ''.join(res)

