Daily LeetCode #6

https://leetcode.com/problems/longest-happy-string/description/?envType=daily-question&envId=2024-10-16

This question requires excuting many conditions.

The basic idea is:

• use a min pq to allow us retrive the one with largest value
• pq stores int[] in form of `(num, int that indicates the letter)'
• if there are no two same consecutive letters in res, we add current letter and put it back to pq with its num - 1
• if there are two same consecutive letters in res, we poll the second largest one from pq, and put the original one back after the operations on the second one finish
• need to check pq.isEmpty() when polling the second one
• if the current one polled from pq has num = 0, we should stop since even the max one is not available

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        String res = "";
        // use max pq
        PriorityQueue<int[]> pq = new PriorityQueue<>((m, n) -> Integer.compare(n[0], m[0]));

        // initialize pq
        if (a != 0) pq.offer(new int[]{a, 0});
        if (b != 0) pq.offer(new int[]{b, 1});
        if (c != 0) pq.offer(new int[]{c, 2});

        String[] letters = {"a", "b", "c"};

        // last: last letter
        int last = -1;
        // now: current letter
        int now = -1;
        // n: number of consecutive same letters
        int n = 0;

        while(!pq.isEmpty()) {
            int[] curr = pq.poll();
            now = curr[1];
            int num = curr[0];
            n = (now == last) ? n + 1 : 1;
            
            // n < 3 ensures no three same consecutive letters
            if(n < 3) {
                if(num > 0) {
                    res += letters[now];
                    num--;
                    last = now;

                    pq.offer(new int[]{num, now});
                
                // if the current max in pq has num 0, no char can be added to res
                } else {
                    break;
                }

            } else {
                // ensure still have element to poll from pq
                if(!pq.isEmpty()) {
                    // when already have two same consecutive letters, choose the next max
                    int[] newCurr = pq.poll();
                    now = newCurr[1];
                    num = newCurr[0];

                    if(num > 0) {
                        res += letters[now];
                        num--;
                        last = now;
                        
                        pq.offer(new int[]{num, now});
                        
                    } else {
                        break;
                    }

                    // put the first polled one back in pq
                    pq.offer(curr);
                    } else {
                        break;
                    } 
            }
        }
        return res;
    }
}

Time Complexity: O(nlogn) , where n = a + b + c.

[pq operation is O(logn), and we have at most a+b+c operations]

Space Complexity: O(n)