题目

类型：贪心

解题思路

每次都取当前剩余次数最多的字符来进行构造（前提是满足「不出现形如 aaa 字符串」的要求）。

可以使用「优先队列（堆）」来实现上述过程，以 （字符编号, 字符剩余数量） 的二元组形式进行存储，构建以 字符剩余数量 排倒序的「大根堆」：

• 起始先将 (0, a)、(1, b) 和 (2, c) 进行入堆（其中 123 为字符编号，代指 abc，同时规定只有剩余数量大于 0 才能入堆）；
• 每次取出堆顶元素（剩余数量最多的字符），尝试参与答案的构造：
  • 不违反连续三个字符相同：则说明当前字符能够追加到当前答案尾部，若追加后还有字符剩余，则更新剩余数量重新入堆；
  • 违反连续三个字符相同：说明该字符无法追加到当前答案尾部，此时尝试从堆中取出剩余次数次大的字符（若当前堆为空，说明没有任何合法字符能够追加，直接 break），若次大字符追加后还有字符剩余，则更新剩余数量重新入堆，同时将此前取的最大字符元祖也重新入堆；
• 重复步骤 2，直到所有字符均被消耗，或循环提前结束。

该做法的正确性：当 时能够确保所有字符轮流参与构建，得到长度最大的快乐字符串，而该贪心策略（每次尽可能地进行大数消减）可以确保能够尽可能的凑成 a = b = c 的局面，并且凑成该局面过程中不会从有解变为无解。

代码

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> q = new PriorityQueue<>((x,y)->y[1]-x[1]);
        if (a > 0) q.add(new int[]{0, a});
        if (b > 0) q.add(new int[]{1, b});
        if (c > 0) q.add(new int[]{2, c});
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int n = sb.length();
            if (n >= 2 && sb.charAt(n - 1) - 'a' == cur[0] && sb.charAt(n - 2) - 'a' == cur[0]) {
                if (q.isEmpty()) break;
                int[] next = q.poll();
                sb.append((char)(next[0] + 'a'));
                if (--next[1] != 0) q.add(next);
                q.add(cur);
            } else {
                sb.append((char)(cur[0] + 'a'));
                if (--cur[1] != 0) q.add(cur);
            }
        }
        return sb.toString();
    }
}