1405. Longest Happy String - cocoder39/coco39_LC GitHub Wiki

1405. Longest Happy String

find the next char in a greedy manner (ie the one with most frequency)

time complexity: (a+b+c) log 3 = (a+b+c)

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        max_heap = []
        if a > 0:
            heapq.heappush(max_heap, (-a, 'a'))
        if b > 0:
            heapq.heappush(max_heap, (-b, 'b'))
        if c > 0:
            heapq.heappush(max_heap, (-c, 'c'))
        
        s = []
        while max_heap:
            count1, char1 = heapq.heappop(max_heap)
            if len(s) >= 2 and s[-1] == s[-2] == char1:
                if not max_heap:
                    return ''.join(s)
                count2, char2 = heapq.heappop(max_heap)
                s.append(char2)
                count2 += 1
                if count2 != 0:
                    heapq.heappush(max_heap, (count2, char2))
                heapq.heappush(max_heap, (count1, char1))
            else:
                s.append(char1)
                count1 += 1
                if count1 != 0:
                    heapq.heappush(max_heap, (count1, char1))
        
        return ''.join(s)