|
| 1 | +### 题目描述 |
| 2 | + |
| 3 | +这是 LeetCode 上的 **[1405. 最长快乐字符串](https://leetcode-cn.com/problems/longest-happy-string/solution/gong-shui-san-xie-jie-he-you-xian-dui-li-q6fd/)** ，难度为 **中等**。 |
| 4 | + |
| 5 | +Tag : 「优先队列（堆）」、「贪心」 |
| 6 | + |
| 7 | + |
| 8 | + |
| 9 | +如果字符串中不含有任何 `'aaa'`，`'bbb'` 或 `'ccc'` 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。 |
| 10 | + |
| 11 | +给你三个整数 `a`，`b` ，`c`，请你返回 任意一个 满足下列全部条件的字符串 `s`： |
| 12 | + |
| 13 | +* `s` 是一个尽可能长的快乐字符串。 |
| 14 | +* `s` 中 最多 有 `a` 个字母 `'a'`、`b` 个字母 `'b'`、`c` 个字母 `'c'` 。 |
| 15 | +* `s` 中只含有 `'a'`、`'b'` 、`'c'` 三种字母。 |
| 16 | + |
| 17 | +如果不存在这样的字符串 `s` ，请返回一个空字符串 `""`。 |
| 18 | + |
| 19 | +示例 1： |
| 20 | +``` |
| 21 | +输入：a = 1, b = 1, c = 7 |
| 22 | +
|
| 23 | +输出："ccaccbcc" |
| 24 | +
|
| 25 | +解释："ccbccacc" 也是一种正确答案。 |
| 26 | +``` |
| 27 | +示例 2： |
| 28 | +``` |
| 29 | +输入：a = 2, b = 2, c = 1 |
| 30 | +
|
| 31 | +输出："aabbc" |
| 32 | +``` |
| 33 | +示例 3： |
| 34 | +``` |
| 35 | +输入：a = 7, b = 1, c = 0 |
| 36 | +
|
| 37 | +输出："aabaa" |
| 38 | +
|
| 39 | +解释：这是该测试用例的唯一正确答案。 |
| 40 | +``` |
| 41 | + |
| 42 | +提示： |
| 43 | +* $0 <= a, b, c <= 100$ |
| 44 | +* $a + b + c > 0$ |
| 45 | + |
| 46 | +--- |
| 47 | + |
| 48 | +### 贪心 |
| 49 | + |
| 50 | +容易想到：**每次都取当前剩余次数最多的字符来进行构造（前提是满足「不出现形如 `aaa` 字符串」的要求）**。 |
| 51 | + |
| 52 | +具体的，可以使用「优先队列（堆）」来实现上述过程，以 `（字符编号, 字符剩余数量）` 的二元组形式进行存储，构建以 `字符剩余数量` 排倒序的「大根堆」： |
| 53 | + |
| 54 | +1. 起始先将 $(0, a)$、$(1, b)$ 和 $(2, c)$ 进行入堆（其中 $123$ 为字符编号，代指 `abc`，同时规定只有剩余数量大于 $0$ 才能入堆）； |
| 55 | +2. 每次取出堆顶元素（剩余数量最多的字符），尝试参与答案的构造： |
| 56 | + 1. 不违反连续三个字符相同：则说明当前字符能够追加到当前答案尾部，若追加后还有字符剩余，则更新剩余数量重新入堆； |
| 57 | + 2. 违反连续三个字符相同：说明该字符无法追加到当前答案尾部，此时尝试从堆中取出剩余次数次大的字符（若当前堆为空，说明没有任何合法字符能够追加，直接 break），若次大字符追加后还有字符剩余，则更新剩余数量重新入堆，同时将此前取的最大字符元祖也重新入堆； |
| 58 | +3. 重复步骤 $2$，直到所有字符均被消耗，或循环提前结束。 |
| 59 | + |
| 60 | +该做法的正确性：**当 $a = b = c$ 时能够确保所有字符轮流参与构建，得到长度最大的快乐字符串，而该贪心策略（每次尽可能地进行大数消减）可以确保能够尽可能的凑成 $a = b = c$ 的局面，并且凑成该局面过程中不会从有解变为无解。** |
| 61 | + |
| 62 | +代码： |
| 63 | +```Java |
| 64 | +class Solution { |
| 65 | + public String longestDiverseString(int a, int b, int c) { |
| 66 | + StringBuilder sb = new StringBuilder(); |
| 67 | + PriorityQueue<int[]> q = new PriorityQueue<>((x,y)->y[1]-x[1]); |
| 68 | + if (a > 0) q.add(new int[]{0, a}); |
| 69 | + if (b > 0) q.add(new int[]{1, b}); |
| 70 | + if (c > 0) q.add(new int[]{2, c}); |
| 71 | + while (!q.isEmpty()) { |
| 72 | + int[] cur = q.poll(); |
| 73 | + int n = sb.length(); |
| 74 | + if (n >= 2 && sb.charAt(n - 1) - 'a' == cur[0] && sb.charAt(n - 2) - 'a' == cur[0]) { |
| 75 | + if (q.isEmpty()) break; |
| 76 | + int[] next = q.poll(); |
| 77 | + sb.append((char)(next[0] + 'a')); |
| 78 | + next[1]--; |
| 79 | + if (next[1] != 0) q.add(next); |
| 80 | + q.add(cur); |
| 81 | + } else { |
| 82 | + sb.append((char)(cur[0] + 'a')); |
| 83 | + cur[1]--; |
| 84 | + if (cur[1] != 0) q.add(cur); |
| 85 | + } |
| 86 | + } |
| 87 | + return sb.toString(); |
| 88 | + } |
| 89 | +} |
| 90 | +``` |
| 91 | +* 时间复杂度：令答案最大长度为 $n = a + b + c$，优先队列中最多有 $C = 3$ 个元素，复杂度为 $O(n * k * \log{C})$，其中 $k$ 为构造答案字符串中每个字符所需要的平均「出队 + 入队」次数，$k$ 为一个范围在 $[2,4]$ 的数字 |
| 92 | +* 空间复杂度：$O(C)$ |
| 93 | + |
| 94 | +--- |
| 95 | + |
| 96 | +### 最后 |
| 97 | + |
| 98 | +这是我们「刷穿 LeetCode」系列文章的第 `No.1405` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。 |
| 99 | + |
| 100 | +在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 |
| 101 | + |
| 102 | +为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。 |
| 103 | + |
| 104 | +在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 |
| 105 | + |
0 commit comments