1405. Longest Happy String

T: O(nlogn), n is a+b+c

S: O(n)

class Solution {
    private record Count(int count, char c){};
    public String longestDiverseString(int a, int b, int c) {
        // use most freq first
        Queue<Count> pq = new PriorityQueue<>((x, y) -> y.count - x.count);
        if (a > 0) {
            pq.offer(new Count(a, 'a'));
        }
        if (b > 0) {
            pq.offer(new Count(b, 'b'));
        }
        if (c > 0) {
            pq.offer(new Count(c, 'c'));
        }

        StringBuilder result = new StringBuilder();
        while (!pq.isEmpty()) {
            Count cur = pq.poll();
            int curCount = cur.count;

            int len = result.length();
            if (len >= 2 && result.charAt(len-1) == cur.c && result.charAt(len-2) == cur.c) {
                if (pq.isEmpty()) {
                    break;
                }

                Count next = pq.poll();
                result.append(next.c);
                if (next.count-1 > 0) { 
                    pq.offer(new Count(next.count-1, next.c));
                }
            } else {
                result.append(cur.c);
                curCount--;
            }

            if (curCount > 0) { 
                pq.offer(new Count(curCount, cur.c));
            }
        }

        return result.toString();
    }
}

/**
T: O(nlogn)
 */

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        pq = []
        if a > 0:
            heapq.heappush(pq, (-a, 'a'))
        if b > 0:
            heapq.heappush(pq, (-b, 'b'))
        if c > 0:
            heapq.heappush(pq, (-c, 'c'))

        result = []
        while pq:
            count, character = heapq.heappop(pq);
            count = -count
            if len(result) >= 2 and result[-1] == character and result[-2] == character:
                if not pq:
                    break

                next_count, next_character = heapq.heappop(pq);
                next_count = -next_count
                result.append(next_character)
                if next_count - 1 > 0:
                    heapq.heappush(pq, (-next_count+1, next_character))
            else:
                count -= 1
                result.append(character)

            if count > 0:
                heapq.heappush(pq, (-count, character))

        return "".join(result)