lc1405. 最长快乐字符串（贪心（优先队列））

如果字符串中不含有任何 ‘aaa’，’bbb’ 或 ‘ccc’ 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

s 是一个尽可能长的快乐字符串。
s 中 最多 有a 个字母 ‘a’、b 个字母 ‘b’、c 个字母 ‘c’ 。
s 中只含有 ‘a’、’b’ 、’c’ 三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 “”。

示例 1：

输入：a = 1, b = 1, c = 7
输出：”ccaccbcc”
解释：”ccbccacc” 也是一种正确答案。
示例 2：

输入：a = 2, b = 2, c = 1
输出：”aabbc”
示例 3：

输入：a = 7, b = 1, c = 0
输出：”aabaa”
解释：这是该测试用例的唯一正确答案。

提示：

0 <= a, b, c <= 100
a + b + c > 0

class Solution {
    /**
    该做法的正确性：当 a=b=c !=0 时能够确保所有字符轮流参与构建，得到长度最大的快乐字符串，而该贪心策略（每次尽可能地进行大数消减）可以确保能够尽可能的凑成 a = b = ca=b=c 的局面，并且凑成该局面过程中不会从有解变为无解。
     */
    public String longestDiverseString(int a, int b, int c) {
        StringBuilder res = new StringBuilder();
        PriorityQueue<int[]> pq = new PriorityQueue<>((x,y) -> y[1]-x[1]);
        if (a > 0) pq.add(new int[]{0,a});
        if (b > 0) pq.add(new int[]{1,b});
        if (c > 0) pq.add(new int[]{2,c});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int n = res.length();
            //如果大的字母已经不能继续构建就判断次大数组
            if (n >= 2 && res.charAt(n-1) == cur[0] + 'a' && res.charAt(n-2) == cur[0] + 'a') {
                //如果pq为空代表不能再组建数组了直接返回
                if (pq.isEmpty()) break;
                int[] next = pq.poll();
                res.append((char)(next[0]+'a'));
                if (--next[1] > 0) pq.add(next);
                pq.add(cur);
            } else {
                res.append((char)(cur[0]+'a'));
                if (--cur[1] > 0) pq.add(cur);
            }
        }
        return res.toString();
    }
}