LeetCode 1405. 最长快乐字符串
目录
题目描述
题意分析
给定三个整数
a、b、c，分别表示可用的'a'、'b'、'c'的数量上限。要构造一个尽可能长的字符串，满足两个条件：不含"aaa"、"bbb"、"ccc"任一子串；每种字符的使用次数不超过对应上限。返回任意一个最长解，若无法构造出非空串则返回空串。两个约束的性质完全不同。「不含三连」是局部约束——只与结尾两个字符有关，与更早的历史无关；「用量不超上限」是全局约束——是三个独立的资源上限。把它们分开看，问题就变成「在局部禁令下最大化资源消耗」。
「返回任意一个最长解」这句话很重要：不需要字典序最小，也不需要与某个特定答案一致，只要长度最大且合法即可。这允许贪心地做局部决策而不必回溯比较。
注意上限是「不超过」而不是「必须用完」。很多情况下某种字符会有剩余用不掉，比如
a = 7, b = 1, c = 0时最多只能排出"aabaa"，还剩三个'a'。所以答案长度不是a + b + c。约束里
a、b、c都在[0, 100]范围内，总长度最多 300。规模极小，但这道题考的是贪心策略的正确性而不是效率。边界要留意四点：三个数可能全为 0，此时返回空串；可能只有一种字符非零，此时最多输出两个；某种字符数量远超其他两者之和时，多出的部分必然浪费；结果字符串本身也可能因为「无字符可用」而提前终止。
解法：最大堆贪心
核心思路
最大堆按剩余数量保存三种字符。每轮优先取数量最多的字符：它最可能因为缺少分隔符而在最后剩余，应尽早消耗。
若堆顶字符会与结果末尾两个字符组成三连，它当前一定不能选。此时取剩余数量第二多的字符放一个，再把堆顶放回；如果没有第二种字符，任何字符都无法追加，算法结束。只放一个替代字符就足以解除三连限制，也不会多消耗稀缺的分隔符。
安全不变量是：结果始终不含三个连续相同字符，且堆中计数与尚未使用的字符数完全一致。每次追加前检查三连、追加后只减少对应计数，因此不变量持续成立。
最长性可以用“最大字符与分隔符”解释。设初始最多的字符有 $M$ 个，另外两种共有 $R$ 个。其他字符形成 $R+1$ 个空隙，每个空隙至多放两个最多字符，因此该字符最多使用 $2(R+1)$ 个。贪心在合法时优先消耗当前最多字符；被阻塞时只使用一个必要的替代字符来新建空隙，不会浪费分隔能力。若堆最终清空，显然使用了全部字符；若提前停止，则只剩一种字符且末尾已经有两个该字符，所有分隔字符均已使用，已经达到上述空隙上界，无法构造更长结果。
解题步骤
- 把计数大于 0 的字符放进最大堆。
- 弹出堆顶
first，检查追加后是否三连。- 若合法，追加
first，计数减一后按需放回。- 若不合法且堆非空，弹出
second追加并更新，再把未使用的first原样放回。- 若不合法且没有
second，立即结束。
a = 1, b = 1, c = 7时，算法会用'a'、'b'分隔'c'，得到长度 8 的快乐字符串，并留下一个无法放置的'c'。上界为 $R+2(R+1)=2+6=8$，因此结果最长。边界
a = 7, b = 1, c = 0的上界是 $1+2(1+1)=5$，算法在得到类似"aabaa"后发现只剩'a'且末尾为"aa"，正确停止。
代码实现
import java.util.PriorityQueue;
class Solution {
public String longestDiverseString(int a, int b, int c) {
PriorityQueue<int[]> pq = new PriorityQueue<>(
(x, y) -> Integer.compare(y[0], x[0]));
if (a > 0) {
pq.offer(new int[] {a, 'a'});
}
if (b > 0) {
pq.offer(new int[] {b, 'b'});
}
if (c > 0) {
pq.offer(new int[] {c, 'c'});
}
StringBuilder sb = new StringBuilder(a + b + c);
while (!pq.isEmpty()) {
int[] first = pq.poll();
int n = sb.length();
if (n >= 2 && sb.charAt(n - 1) == first[1] && sb.charAt(n - 2) == first[1]) {
if (pq.isEmpty()) {
break;
}
int[] second = pq.poll();
sb.append((char) second[1]);
second[0]--;
if (second[0] > 0) {
pq.offer(second);
}
pq.offer(first);
} else {
sb.append((char) first[1]);
first[0]--;
if (first[0] > 0) {
pq.offer(first);
}
}
}
return sb.toString();
}
}
import "container/heap"
type item struct {
count int
char byte
}
type maxHeap []item
func (h maxHeap) Len() int { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i].count > h[j].count }
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x any) { *h = append(*h, x.(item)) }
func (h *maxHeap) Pop() any {
old := *h
last := len(old) - 1
x := old[last]
*h = old[:last]
return x
}
func longestDiverseString(a int, b int, c int) string {
h := &maxHeap{}
if a > 0 {
heap.Push(h, item{count: a, char: 'a'})
}
if b > 0 {
heap.Push(h, item{count: b, char: 'b'})
}
if c > 0 {
heap.Push(h, item{count: c, char: 'c'})
}
res := make([]byte, 0, a+b+c)
for h.Len() > 0 {
first := heap.Pop(h).(item)
n := len(res)
if n >= 2 && res[n-1] == first.char && res[n-2] == first.char {
if h.Len() == 0 {
break
}
second := heap.Pop(h).(item)
res = append(res, second.char)
second.count--
if second.count > 0 {
heap.Push(h, second)
}
heap.Push(h, first)
} else {
res = append(res, first.char)
first.count--
if first.count > 0 {
heap.Push(h, first)
}
}
}
return string(res)
}
复杂度分析
- 时间复杂度：$O(N)$，其中 $N=a+b+c$。每轮追加一个字符，堆大小至多为 3，堆操作为常数时间。
- 空间复杂度：$O(N)$ 用于结果；不计返回值时，最大堆只保存三项，额外空间为 $O(1)$。
关键点总结
- 最大堆优先消耗剩余最多的字符，控制最危险的数量失衡。
- 只有结果末尾已连续出现两次堆顶字符时，才改用第二多字符。
- 替代字符放一个即可解除限制，未使用的堆顶计数不能减少。
- 堆顶受阻且没有第二项时已无法继续，必须结束而不是反复放回。
- 最多字符可使用的上界是 $2(R+1)$，可用于解释结果为何达到最大长度。
易错点总结
- 不检查末尾两个字符就始终取堆顶，
a = 3, b = 0, c = 0会生成非法的"aaa"。- 堆顶受阻且堆已空时仍将其放回，会在
a = 7, b = 0, c = 0上死循环。- 改用第二项后忘记放回未使用的堆顶，会丢失大量仍可用字符。
- 数量减到 0 后仍放回堆，会超出对应字符的使用上限。
- 比较器写成小顶堆会优先耗尽稀缺分隔符；
a = 1, b = 1, c = 7将无法达到长度 8。- 认为所有字符都必须用完。
a = 7, b = 1, c = 0最长长度只有 5。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 767. 重构字符串 | 中等 | 要求相邻字符全不相同（限制更严），且必须用完所有字符，无解时返回空串 |
| 621. 任务调度器 | 中等 | 同种任务间需隔 n 个单位，可用桶思想直接推出公式而不必模拟 |
| 984. 不含 AAA 或 BBB 的字符串 | 中等 | 只有两种字符且必须全部用完，贪心规则可以简化成固定的成对输出 |
| 451. 根据字符出现频率排序 | 中等 | 只按频次降序输出、没有相邻限制，是本题去掉局部约束后的最简版本 |
| 347. 前 K 个高频元素 | 中等 | 频次统计 + 堆取前 K，训练「用堆维护动态最值」的基本功 |
| 692. 前K个高频单词 | 中等 | 频次相同时还要按字典序，考察复合比较器的写法 |
| 215. 数组中的第K个最大元素 | 中等 | 固定大小堆与快速选择的取舍，是堆类题的基础 |
| 1642. 可以到达的最远建筑 | 中等 | 用堆动态反悔之前的贪心选择，展示贪心 + 堆的另一种组合方式 |
| 502. IPO | 困难 | 双堆配合：一个按门槛排序解锁候选，一个按收益取最大，同为「资源受限下的贪心」 |
| 253. 会议室 II | 中等 | 用最小堆维护正在占用的资源，训练「弹出已释放资源」的思路 |
| 23. 合并 K 个升序链表 | 困难 | 堆里始终保留每路的当前头，用完即补，与本题「用完即出局」结构相似 |
| 295. 数据流的中位数 | 困难 | 双堆维持平衡，说明堆不只用于取最值，还能维护分布 |
| 1328. 破坏回文串 | 中等 | 同为字符串上的贪心构造，重点是字典序而非长度 |
| 316. 去除重复字母 | 中等 | 贪心 + 单调栈构造字符串，需要结合剩余计数判断能否弹出 |