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

Difficulty: interview

Starter code:

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        

Solutions:
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        if a == 0 and b == 0 and c == 0:
            return ''

        res = ''

        heap = [(-a, 'a'), (-b, 'b'), (-c, 'c')]
        heapq.heapify(heap)
        prev_val = 0
        prev_char = ''

        while heap:
            v, char = heapq.heappop(heap)
            if prev_val < 0:
                heapq.heappush(heap, (prev_val, prev_char))

            if abs(v) >= 2:
                if abs(v) > abs(prev_val):
                    res += char*2
                    v += 2
                else:
                    res += char
                    v += 1
            elif abs(v) == 1:
                res += char
                v +=1
            elif abs(v) == 0:
                break

            prev_val = v
            prev_char = char

        return res

class Solution:
    # https://leetcode.com/problems/longest-happy-string/discuss/564277/C%2B%2BJava-a-greater-b-greater-c
    def longestDiverseString(self, a: int, b: int, c: int, charA = 'a', charB = 'b', charC = 'c') -> str:
        if a<b: 
            return self.longestDiverseString(b, a, c, charB, charA, charC)
        if b<c: 
            return self.longestDiverseString(a, c, b, charA, charC, charB)
        # print(a, b, c, charA, charB, charC)
        if b==0: 
            return min(a, 2)*charA 
        use_a = min(2, a)
        use_b = 1 if a-use_a>=b else 0 
        return charA*use_a + charB*use_b + self.longestDiverseString(a-use_a, b-use_b, c, charA, charB, charC)

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)