| [987. 二叉树的垂序遍历](https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-dfs-h-wfm3/) | 困难 | 🤩🤩🤩🤩🤩 |

| [1005. K 次取反后最大化的数组和](https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/solution/gong-shui-san-xie-jian-dan-fen-qing-kuan-6qwu/) | 简单 | 🤩🤩🤩🤩 |

| [1337. 矩阵中战斗力最弱的 K 行](https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix/solution/gong-shui-san-xie-yi-ti-shuang-jie-po-su-7okx/) | 简单 | 🤩🤩🤩 |

| [1405. 最长快乐字符串](https://leetcode-cn.com/problems/longest-happy-string/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/longest-happy-string/solution/gong-shui-san-xie-jie-he-you-xian-dui-li-q6fd/) | 中等 | 🤩🤩🤩🤩 |

| [1705. 吃苹果的最大数目](https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-hfdy0/) | 中等 | 🤩🤩🤩🤩🤩 |

| [1834. 单线程 CPU](https://leetcode-cn.com/problems/single-threaded-cpu/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/single-threaded-cpu/solution/gong-shui-san-xie-shu-ju-jie-gou-yun-yon-1qk0/) | 中等 | 🤩🤩🤩🤩 |

| [面试题 17.14. 最小K个数](https://leetcode-cn.com/problems/smallest-k-lcci/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/smallest-k-lcci/solution/gong-shui-san-xie-yi-ti-si-jie-you-xian-yy5k5/) | 中等 | 🤩🤩🤩🤩 |

| [1005. K 次取反后最大化的数组和](https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/solution/gong-shui-san-xie-jian-dan-fen-qing-kuan-6qwu/) | 简单 | 🤩🤩🤩🤩 |

| [1218. 最长定差子序列](https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/solution/gong-shui-san-xie-jie-he-tan-xin-de-zhua-dj1k/) | 中等 | 🤩🤩🤩🤩🤩 |

| [1221. 分割平衡字符串](https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-wumnk/) | 简单 | 🤩🤩🤩🤩 |

| [1405. 最长快乐字符串](https://leetcode-cn.com/problems/longest-happy-string/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/longest-happy-string/solution/gong-shui-san-xie-jie-he-you-xian-dui-li-q6fd/) | 中等 | 🤩🤩🤩🤩 |

| [1414. 和为 K 的最少斐波那契数字数目](https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-rgty8/) | 中等 | 🤩🤩🤩🤩 |

| [1705. 吃苹果的最大数目](https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-hfdy0/) | 中等 | 🤩🤩🤩🤩🤩 |

| [1707. 与数组中元素的最大异或值](https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/solution/gong-shui-san-xie-jie-zhe-ge-wen-ti-lai-lypqr/) | 困难 | 🤩🤩🤩 |

这是 LeetCode 上的 **[1405. 最长快乐字符串](https://leetcode-cn.com/problems/longest-happy-string/solution/gong-shui-san-xie-jie-he-you-xian-dui-li-q6fd/)** ,难度为 **中等**。

Tag : 「优先队列(堆)」、「贪心」

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

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

* `s` 是一个尽可能长的快乐字符串。

* `s` 中 最多 有 `a` 个字母 `'a'`、`b` 个字母 `'b'`、`c` 个字母 `'c'` 。

* `s` 中只含有 `'a'`、`'b'` 、`'c'` 三种字母。

如果不存在这样的字符串 `s` ,请返回一个空字符串 `""`。

示例 1:

示例 2:

示例 3:

提示:

* 0ドル <= a, b, c <= 100$

* $a + b + c > 0$

容易想到:**每次都取当前剩余次数最多的字符来进行构造(前提是满足「不出现形如 `aaa` 字符串」的要求)**。

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

1. 起始先将 $(0, a)$、$(1, b)$ 和 $(2, c)$ 进行入堆(其中 123ドル$ 为字符编号,代指 `abc`,同时规定只有剩余数量大于 0ドル$ 才能入堆);

2. 每次取出堆顶元素(剩余数量最多的字符),尝试参与答案的构造:

1. 不违反连续三个字符相同:则说明当前字符能够追加到当前答案尾部,若追加后还有字符剩余,则更新剩余数量重新入堆;

2. 违反连续三个字符相同:说明该字符无法追加到当前答案尾部,此时尝试从堆中取出剩余次数次大的字符(若当前堆为空,说明没有任何合法字符能够追加,直接 break),若次大字符追加后还有字符剩余,则更新剩余数量重新入堆,同时将此前取的最大字符元祖也重新入堆;

3. 重复步骤 2ドル,ドル直到所有字符均被消耗,或循环提前结束。

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

代码:

class Solution {

public String longestDiverseString(int a, int b, int c) {

StringBuilder sb = new StringBuilder();

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});

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'));

next[1]--;

if (next[1] != 0) q.add(next);

q.add(cur);

} else {

sb.append((char)(cur[0] + 'a'));

cur[1]--;

if (cur[1] != 0) q.add(cur);

}

}

return sb.toString();

}

}

* 时间复杂度:令答案最大长度为 $n = a + b + c,ドル优先队列中最多有 $C = 3$ 个元素,复杂度为 $O(n * k * \log{C}),ドル其中 $k$ 为构造答案字符串中每个字符所需要的平均「出队 + 入队」次数,$k$ 为一个范围在 $[2,4]$ 的数字

* 空间复杂度:$O(C)$

这是我们「刷穿 LeetCode」系列文章的第 `No.1405` 篇,系列开始于 2021年01月01日,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。