力扣1405.最长快乐字符串

题目

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

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

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

示例

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

输入：a = 2, b = 2, c = 1
输出：“aabbc”

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-happy-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：优先队列+贪心

Java实现

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