§1

题目描述

看清楚两个约束:第一,字母 a 最多放 1 个、b 最多 1 个、c 最多 7 个,可以少放、不能超;第二,任何时候都不能让三个相同字母挨在一起,也就是不许出现 aaa、bbb、ccc。在这两条下面,把串拼得越长越好。注意答案不要求把所有字母都用完,用不下的就剩着。比如 a = 1,b = 1,c = 7 时,c 太多了,塞不下,最后会有一个 c 用不上。本节就一步步拼出 "ccaccbcc"。

输入 = a=1, b=1, c=7　输出 = ccaccbcc

输入 = a=2, b=2, c=1　输出 = ababc

输入 = a=0, b=0, c=1　输出 = c

§2

思路解析动画文字版

记牢两句:优先放剩余最多的字母;但末尾已经两个相同时就跳过它、改放次多的。下面每一位都在套这两句。

总览 · 三个字母的库存摆好,从左往右一位一位拼：上面这排是要拼的串,现在全是占位点 ·,一位都还没填。右边面板是三个字母的剩余可用次数:a 有 1 个,b 有 1 个,c 有 7 个。c 明显最多。接下来从最左边开始,每一位都贪心地挑剩余最多、又不会凑成三连的字母填进去。

第 0 位 · 先看谁剩得最多：填第一位。三个字母按剩余次数从多到少排:c 有 7、a 有 1、b 有 1。c 最多,而且串还空着,放 c 不会三连,就先拿 c。

第 0 位 · 填入 c：把 c 填进第 0 位,亮起来的就是它。c 的剩余次数从 7 减到 6。现在串是 "c"。继续看下一位。

第 1 位 · 先看谁剩得最多：填第 1 位。眼下剩余排序是 c 有 6 个、a 有 1 个、b 有 1 个。剩最多的是 c,先看它放进去会不会三连。

第 1 位 · 填入 c：把 c 填进第 1 位,亮起来的就是它。c 的剩余次数从 6 减到 5。现在串是 "cc"。继续看下一位。

第 2 位 · 先看谁剩得最多：填第 2 位。眼下剩余排序是 c 有 5 个、a 有 1 个、b 有 1 个。剩最多的是 c,可是要先看末尾会不会三连。

第 2 位 · 最多的 c 被三连规则挡住：注意看末尾标红的两位,都是 c。c 虽然剩得最多,可这会儿再放一个就会凑成 ccc,犯规。所以这一位跳过 c,往后挑剩余次多、又不会三连的字母,也就是 a,它还剩 1 个。

第 2 位 · 填入 a：把 a 填进第 2 位,亮起来的就是它。a 的剩余次数从 1 减到 0。现在串是 "cca",a 已经用光了。继续看下一位。

第 3 位 · 先看谁剩得最多：填第 3 位。眼下剩余排序是 c 有 5 个、b 有 1 个、a 有 0 个。剩最多的是 c,先看它放进去会不会三连。

第 3 位 · 填入 c：把 c 填进第 3 位,亮起来的就是它。c 的剩余次数从 5 减到 4。现在串是 "ccac"。继续看下一位。

第 4 位 · 先看谁剩得最多：填第 4 位。眼下剩余排序是 c 有 4 个、b 有 1 个、a 有 0 个。剩最多的是 c,先看它放进去会不会三连。

第 4 位 · 填入 c：把 c 填进第 4 位,亮起来的就是它。c 的剩余次数从 4 减到 3。现在串是 "ccacc"。继续看下一位。

第 5 位 · 先看谁剩得最多：填第 5 位。眼下剩余排序是 c 有 3 个、b 有 1 个、a 有 0 个。剩最多的是 c,可是要先看末尾会不会三连。

第 5 位 · 最多的 c 被三连规则挡住：注意看末尾标红的两位,都是 c。c 虽然剩得最多,可这会儿再放一个就会凑成 ccc,犯规。所以这一位跳过 c,往后挑剩余次多、又不会三连的字母,也就是 b,它还剩 1 个。

第 5 位 · 填入 b：把 b 填进第 5 位,亮起来的就是它。b 的剩余次数从 1 减到 0。现在串是 "ccaccb",b 已经用光了。继续看下一位。

第 6 位 · 先看谁剩得最多：填第 6 位。眼下剩余排序是 c 有 3 个、a 有 0 个、b 有 0 个。剩最多的是 c,先看它放进去会不会三连。

第 6 位 · 填入 c：把 c 填进第 6 位,亮起来的就是它。c 的剩余次数从 3 减到 2。现在串是 "ccaccbc"。继续看下一位。

第 7 位 · 先看谁剩得最多：填第 7 位。眼下剩余排序是 c 有 2 个、a 有 0 个、b 有 0 个。剩最多的是 c,先看它放进去会不会三连。

第 7 位 · 填入 c：把 c 填进第 7 位,亮起来的就是它。c 的剩余次数从 2 减到 1。现在串是 "ccaccbcc"。继续看下一位。

第 8 位 · 先看谁剩得最多：填第 8 位。眼下剩余排序是 c 有 1 个、a 有 0 个、b 有 0 个。剩最多的是 c,可是要先看末尾会不会三连。

收尾 · 谁都放不下了,停：到这一步,串末尾是 cc,只有 c 还剩 1 个,可再放一个 c 就会凑成三连,不行;a 和 b 都已经用光。三个字母谁都放不进去,贪心结束。这就是题目说的「用不下就剩着」,最后这 1 个 c 没能用上。拼好的串是 "ccaccbcc"。

完成 · 答案 "ccaccbcc"：从左拼到右,贪心每一位都挑剩余最多、又不致三连的字母,中途两次因为末尾两个 c 而跳过 c、改放 a 和 b 把它们隔开。最后拼出 "ccaccbcc",长度 8,里面没有任何三连,这就是最长的快乐字符串,跟开头说的答案对上了。

边界:某字母为 0 就全程不选;只有一种字母时数量不超过 2 就放完、超过 2 只能放 2 个其余剩下;次数接近时交替放、可以全用上。

面试重点:贪心放最多是为了避免它最后扎堆三连;数量超过其余字母可提供的隔板容量时会剩;推广到多字母用大顶堆维护成 O(n log k)。

§3

参考代码

from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = nextclass Solution:    def longestDiverseString(self, a: int, b: int, c: int) -> str:        counts = {"a": a, "b": b, "c": c}        ans = []        while True:            picked = None            for ch in sorted(counts, key=lambda x: (-counts[x], x)):                if counts[ch] == 0:                    continue                if len(ans) >= 2 and ans[-1] == ans[-2] == ch:                    continue                picked = ch                break            if picked is None:                break            ans.append(picked)            counts[picked] -= 1        return "".join(ans)

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n)，n = a+b+c 是答案最长可能长度。每放一个字母做一轮:排序的只是 a,b,c 三个元素,是常数;挑字母也只扫这三个。总共最多放 n 个字母,所以是线性的 O(n)。注:若推广到 k 种字母用大顶堆维护,则是 O(n log k),本题 k 固定为 3 故为常数因子
空间：O(n)，按峰值算,主要是存答案那个字符串或 StringBuilder,长度最多 n,占 O(n)。除答案之外只用了三个计数和固定几个变量,是常数 O(1);所以不计输出时是 O(1),计输出则 O(n)

§5

易错点

✗ 错误写法：不管三连,每次都死放剩余最多的字母

✓ 正确写法：放最多的之前先看末尾两位是不是已经是它,会三连就跳过、改放次多的

贪心放最多没错,但少了三连这道刹车就会拼出 ccc 这种非法串。像 c 连放两个后,第三位必须先用别的字母把它隔开,否则犯规

✗ 错误写法：以为必须把 a,b,c 全部用完才算对

✓ 正确写法：能放就放、放不下就停,剩下的字母直接丢掉

当某个字母数量远超另两个时根本塞不下。比如 a=1,b=1,c=7,c 最多只能放下 6 个(每两个 c 之间得垫一个别的字母),剩的那 1 个 c 注定用不上,答案长度是 8 不是 9

✗ 错误写法：把刹车条件写成「末尾一个相同就跳过」

✓ 正确写法：是末尾连续两个都相同才跳过,只有一个相同还能再放一个

允许两个连续相同,只是不许三个。末尾是单个 c 时再放一个 c 得到 cc 是合法的,只有已经是 cc 时放第三个才犯规;条件写松成「一个就跳」会拼不长

面试追问把动画讲成自己的话

追问为什么每一位要贪心地放剩余最多的字母,而不是放最少的?

因为剩得最多的字母最危险,它最容易在后面堆成三连把自己卡死。越早、越频繁地把它往外匀,它就越不容易在末尾连续撞上三连;要是先把少的放完,多的那个最后只剩它一种,连续放就必然三连、放不下去,反而拼得更短。所以优先消化最多的,再用次多的去隔开,整体能拼到最长。

追问答案为什么可能用不完所有字母,什么时候会剩?

当某个字母的数量超过另外两个之和能提供的「间隔位」时就会剩。每两个相同字母之间必须垫一个别的,设最多的那个有 m 个、其余共 r 个,那么最多能放下 2 乘 r 加 2 个该字母;超过这个数的部分注定塞不进去,只能剩着。比如 a=1,b=1,c=7,其余只有 2 个,c 最多放 6 个,剩 1 个 c 用不上,答案长度 8。

追问如果不是三种字母,而是任意多种字母,这套贪心还成立吗,复杂度怎么变?

思路一样:每一位放当前剩余最多、且不会和末尾凑成三连的字母。区别在于字母多了,不能每轮都把全部排一遍,通常改用一个大顶堆按剩余次数维护:弹出堆顶,如果它正好会三连就先弹第二个来放、再把堆顶压回去。这样每放一个字母是 O(log k),k 是字母种类数,总复杂度 O(n log k)。本题 k 固定是 3,排三个元素是常数,所以退化成 O(n)。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 堆套路 13/28

可以到达的最远建筑

LeetCode 1642 · 中等 · 沿着堆套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def longestDiverseString(self, a: int, b: int, c: int) -> str: counts = {"a": a, "b": b, "c": c} ans = [] while True: picked = None for ch in sorted(counts, key=lambda x: (-counts[x], x)): if counts[ch] == 0: continue if len(ans) >= 2 and ans[-1] == ans[-2] == ch: continue picked = ch break if picked is None: break ans.append(picked) counts[picked] -= 1 return "".join(ans)

最长快乐字符串

题目描述

思路解析动画文字版

参考代码

复杂度

易错点

面试追问把动画讲成自己的话

可以到达的最远建筑

把这道题真正学会，再走

最长快乐字符串

题目描述

思路解析动画文字版

参考代码

复杂度

易错点

面试追问把动画讲成自己的话

可以到达的最远建筑

把这道题真正学会，再走