LeetCode 1405. 最长快乐字符串
题目描述
题意分析
最多分别使用给定数量的
a、b、c，构造尽可能长的字符串，要求任意位置都不能出现三个连续相同的字符。允许连续两个相同字符，也允许某些字符没有用完。只要求长度最大，不要求字典序最小，多个最长结果都正确。因此目标既要保证每一步追加合法，也要避免过早耗尽用于分隔数量最多字符的其他字符。
解法：最大堆贪心
核心思路
[!blue]
用最大堆保存仍有剩余的字符及数量，每次优先处理剩余数量最多的一种。数量越多，越需要其他字符把它拆成若干段；先消耗较少的字符，可能提前用掉分隔材料，留下大量同类字符无法放置。
取出最多者后，只需检查结果末尾两位。如果不是同一种字符的双连，就可以追加它一个并减少数量。若已经双连，再放它就会产生三连，只能取堆中第二多的另一种字符作为分隔；放一个就足够，未使用的第一项按原数量放回。
若第一项被双连挡住且堆里已经没有其他字符，当前剩余内容无法再追加，结束构造。最长性不能仅靠这个停止条件，还需要说明数量优先不会把可用长度浪费掉。
设最多的一类有
M个，其余共R个。其他字符最多形成R + 1个容纳该类的间隙，每个间隙最多放两个，因此该类最多使用2 * (R + 1)个。如果M超出这个数量，贪心中的该类会始终占优，每放两个就只消耗一个必要的异类分隔，最终填满所有间隙，达到长度上界R + 2 * (R + 1)。若没有一类超出分隔容量，则所有字符都能安排。更细地看，假设结果末尾已有
t个该类字符，末尾不是该类时t = 0；剩余异类共R个，该类此后最多还能放2 * R + 2 - t个。追加这个最多且合法的字符时，它的剩余数量和允许容量都减少一；若它因t == 2被挡住，放一个异类后，R减一而它的尾部连续数归零，允许容量反而保持不变。其他非首选种类的数量不超过被选中的合法最多者，不会先形成更紧张的分隔需求。因此这个容量条件会随构造保持，可全部使用时不会提前停下。两种情况合起来，贪心都能得到最长长度。
解题步骤
- 将数量大于零的字符加入最大堆。
- 弹出剩余最多者，检查它是否与末尾两个字符相同。
- 不冲突时追加它一个，减少数量，仍有剩余就重新入堆。
- 冲突时，若无其他字符就结束；否则追加第二项一个，更新并放回仍有剩余的第二项，再把第一项原样放回。
- 重复构造，返回结果。
代码实现
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)
}
复杂度分析
设 $N=a+b+c$。
- 时间复杂度：$O(N)$，堆最多三项，单次堆操作为常数时间，每轮至少追加一个字符或直接结束。
- 空间复杂度：$O(N)$，代码按总数量预分配构造缓冲；堆本身只占常数空间，返回字符串之外的构造缓冲也需要计入。
关键点总结
[!green]
- 先消耗剩余最多的合法字符，避免积压难以分隔的多数类。
- 首选被双连限制时只放一个异类，解除限制后再继续竞争数量优先。
- 分隔容量给出最长长度上界，贪心能在无法全用时填满这些间隙。
- 未使用的堆顶保持原计数，只有真正追加的字符才减一。
易错点总结
[!yellow]
- 始终使用堆顶而不检查末尾两位，会产生三个连续相同字符。
- 把限制误写成禁止相邻相同，会丢掉本来允许的双连，缩短结果。
- 使用第二项后忘记放回第一项，会丢失仍然可用的大量字符。
- 没有替代字符时继续反复弹出、放回首选，循环不会推进。
- 数量为零还重新入堆，或者给未使用的首选减计数，都会破坏使用次数约束。
- 题目允许不用完字符，不能为了消耗完输入而追加非法三连。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 984. 不含 AAA 或 BBB 的字符串 | 中等 | 原题只有两种字符且要求全用，本题三种字符可能无法全用，需要最大化合法长度。 |
| 767. 重构字符串 | 中等 | 原题相邻字符就不能相同，本题允许连续两个，贪心选择时需检查最近两位。 |