LC 1405. 最长快乐字符串

题目描述

这是 LeetCode 上的 1405. 最长快乐字符串 ，难度为 中等。

如果字符串中不含有任何 '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$

---

贪心

容易想到：每次都取当前剩余次数最多的字符来进行构造（前提是满足「不出现形如 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 原题链接和其他优选题解。