thảo luận Leetcode mỗi ngày

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {string}
 */
var longestDiverseString = function (a, b, c) {
    const pq = new MaxPriorityQueue();
    pq.enqueue('a', a);
    pq.enqueue('b', b);
    pq.enqueue('c', c);
    let ans = '';
    while (true) {
        let { element: U, priority: u } = pq.dequeue(),
            { element: V, priority: v } = pq.dequeue();
        if (u > 0 && ans.slice(-2) !== U.repeat(2)) {
            ans += U;
            u--;
        } else if (v > 0 && ans.slice(-2) !== V.repeat(2)) {
            ans += V;
            v--;
        } else {
            break;
        }
        pq.enqueue(U, u);
        pq.enqueue(V, v);
    }
    return ans;
};

import heapq


class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        pq = []
        heapq.heappush(pq, (-a, "a"))
        heapq.heappush(pq, (-b, "b"))
        heapq.heappush(pq, (-c, "c"))
        res = [""]
        while pq:
            cnt, char = heapq.heappop(pq)
            if res and res[-1] == char:
                print("I", res, cnt, char, pq)
                if not pq:
                    break
                cnt2, char2 = heapq.heappop(pq)
                m = min(-cnt2, 2)
                # If only two left, take one
                if m == 2 and pq:
                    m -= 1
                cnt2 += m
                while m:
                    res.append(char2)
                    m -= 1
                if cnt2 < 0:
                    heapq.heappush(pq, (cnt2, char2))
                if cnt < 0:
                    heapq.heappush(pq, (cnt, char))
            else:
                print("E", res, cnt, char, pq)
                m = min(-cnt, 2)
                cnt += m
                while m:
                    res.append(char)
                    m -= 1
                if cnt < 0:
                    heapq.heappush(pq, (cnt, char))
        return "".join(res)


if __name__ == "__main__":
    s = Solution()
    print(s.longestDiverseString(1, 1, 7))

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

        maxOccur = max(a, b, c)
        if maxOccur == a:
            if a >= 2:
                result += 'a'
                a -= 1
            result += 'a'
            a -= 1
        elif maxOccur == b:
            if b >= 2:
                result += 'b'
                b -= 1
            result += 'b'
            b -= 1
        else:
            if c >= 2:
                result += 'c'
                c -= 1
            result += 'c'
            c -= 1
        
        while True:
            prev_len = len(result)
            if len(result) == 1:
                maxOccur = max(a, b, c)
                if maxOccur == 0:
                    break
                if maxOccur == a:
                    result += 'a'
                    a -= 1
                elif maxOccur == b:
                    result += 'b'
                    b -= 1
                else:
                    result += 'c'
                    c -= 1
                continue

            if result[-2:] == 'aa':
                maxOccur = max(b, c)
                if maxOccur == 0:
                    break
                if b > c:
                    result += 'b'
                    b -= 1
                else:
                    result += 'c'
                    c -= 1
            elif result[-2:] == 'bb':
                maxOccur = max(a, c)
                if maxOccur == 0:
                    break
                if a > c:
                    result += 'a'
                    a -= 1
                else:
                    result += 'c'
                    c -= 1
            elif result[-2:] == 'cc':
                maxOccur = max(a, b)
                if maxOccur == 0:
                    break
                if a > b:
                    result += 'a'
                    a -= 1
                else:
                    result += 'b'
                    b -= 1
            else:
                maxOccur = max(a, b, c)
                if maxOccur == 0:
                    break
                if maxOccur == a:
                    result += 'a'
                    a -= 1
                elif maxOccur == b:
                    result += 'b'
                    b -= 1
                else:
                    result += 'c'
                    c -= 1
            
            if len(result) == prev_len:
                break
        return result

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        Map<Character, Integer> map = new HashMap<>();
        if (a > 0) {
            map.put('a', a);
        }
        if (b > 0) {
            map.put('b', b);
        }
        if (c > 0) {
            map.put('c', c);
        }
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
        for (Map.Entry<Character, Integer> entry : map.entrySet()) pq.offer(entry);
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry<Character, Integer> entry = pq.poll();
            char character = entry.getKey();
            int count = entry.getValue();
            int len = sb.length();
            if (len >= 2 && sb.charAt(len - 1) == character && sb.charAt(len - 2) == character) {
                if (pq.isEmpty()) break;
                Map.Entry<Character, Integer> tmp = pq.poll();
                sb.append(tmp.getKey());
                if (tmp.getValue() > 1) pq.offer(Map.entry(tmp.getKey(), tmp.getValue() - 1));
            } else {
                count--;
                sb.append(character);
            }
            if (count > 0) {
                pq.offer(Map.entry(character, count));
            }          
        }
        return sb.toString();      
    }
}

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        q = []
        if a != 0:
            heapq.heappush(q, (-a, 'a'))
        if b != 0:
            heapq.heappush(q, (-b, 'b'))
        if c != 0:
            heapq.heappush(q, (-c, 'c'))
        ans = ""
        while q:
            ct, c = heapq.heappop(q)
            if len(ans) >= 2 and ans[len(ans) - 2:] == c + c:
                if q:
                    ct2, c2 = heapq.heappop(q) 
                    ans += c2
                    if ct2 + 1 != 0:
                        heapq.heappush(q,(ct2 + 1, c2))
                    heapq.heappush(q,(ct, c))
                else:
                    return ans
            else:
                
                ans += c
                if ct + 1 != 0:
                    heapq.heappush(q,(ct + 1, c))

        return ans

class Solution {
    class Pair {
        char character;
        int count;
        Pair(char character, int count) {
            this.character = character;
            this.count = count;
        }
    }
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<Pair> pq = new PriorityQueue<>((o1,o2)->o2.count - o1.count);
        if(a > 0) pq.offer(new Pair('a', a));
        if(b > 0) pq.offer(new Pair('b', b));
        if(c > 0) pq.offer(new Pair('c', c));
        StringBuilder ans = new StringBuilder();
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            int count = p.count;
            char character = p.character;
            if (
                ans.length() > 1 &&
                ans.charAt(ans.length() - 1) == p.character &&
                ans.charAt(ans.length() - 2) == p.character
            ) {
                if (pq.isEmpty()) break;

                Pair temp = pq.poll();
                ans.append(temp.character);
                if (temp.count - 1 > 0) {
                    pq.add(new Pair(temp.character,temp.count - 1));
                }
            } else {
                count--;
                ans.append(character);
            }
            if (count > 0) {
                pq.add(new Pair(character,count));
            }
        }
        return ans.toString();
    }
}

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        StringBuilder sb = new StringBuilder();
        //map
        char[] map = new char[4];
        map[1]='a';
        map[2]='b';
        map[3]='c';
        PriorityQueue<int[]> pq = new PriorityQueue<>((x,y)->{
            return y[0]-x[0];
        });
        if(a>0) pq.add(new int[]{a,1});
        if(b>0) pq.add(new int[]{b,2});
        if(c>0) pq.add(new int[]{c,3});
        int[] max = new int[2];
        int[] sec = new int[2];

        while(!pq.isEmpty()){
            if(pq.size()==1){
                max = pq.poll();//max[0] = freq, max[1]= index map
                if(max[0]>1){
                    sb.append(map[max[1]]); max[0]--;
                }
                sb.append(map[max[1]]); max[0]--;
            }
            else{
                max = pq.poll();
                sec = pq.poll();
              
                if(max[0]>sec[0]){
                    sb.append(map[max[1]]); max[0]--;
                }
                sb.append(map[max[1]]); max[0]--;
                sb.append(map[sec[1]]); sec[0]--;
                if(sec[0]>0) pq.add(sec);
                if(max[0]>0) pq.add(max);
              
            }
        }
        return sb.toString();
    }
}