题目描述
思路解析动画文字版
记住这两句:先摆最大、一段至多 repeatLimit 个;放不下还剩就垫一个更小的字母隔开再续。下面一步步套用它。
统计词频 · 答案槽先空着：先数一遍 s 里每个字母出现几次:z 两个、c 四个、a 一个。右边这张小表就是词频桶,从大到小排好 z、c、a,记着各自还剩几个。左边七个方格是答案的位置,现在全空,我们要从最大的字母开始,一个一个把它们填满。
贪心原则 · 高位优先放最大字母：为什么从最大字母下手?比较字典序是从左往右逐位看,谁在越靠前的位上放了更大的字母,谁就更大。所以贪心策略很直接:每一步都在还没放满的最靠前位置,填进当前还有剩的最大字母。此刻最大的是 z,就从 z 开始。
取最大字母 z · 算这一段能连放几个：当前最大字母是 z。一段最多连放 repeatLimit 也就是 3 个,而 z 手头只有 2 个,取两者里小的,这一段就放 2 个 z。因为 2 没到 3,放完 z 正好用光,不需要隔板。开始往前两个空位填 z。
放第 1 个 z → 位置 0：第一个 z 落到位置 0,这是整串的最高位,放上了最大的字母,开局就把字典序顶到最高。右边桶里 z 的剩余从 2 减到 1。这一段目前连续 1 个 z,绿色标出来的就是当前的连续段。
放第 2 个 z → 位置 1 · z 用光：第二个 z 落到位置 1,z 的剩余减到 0,用光了。现在开头是连续两个 z,长度 2,没有超过限制 3,合法。绿色这段清楚地显示了这个连续的 z 段。z 既然摆完,下一步该找比它小的、还有剩的最大字母。
检查 · z 连续 2 个 ≤ 限制 3：回头核对一下这段 z:连续 2 个,规则允许至多 3 个,稳稳合法。答案前两位已经锁定成 z z,这是任何合法串在这两位上能给到的最大字母了。z 用完,接下来看谁是还有剩的最大字母。
z 归零 · 下一个最大可用是 c：词频桶里 z 已经是 0,跳过它。往下看,c 还剩 4 个,是现在最大的可用字母。于是把当前处理对象切到 c。注意 c 有 4 个、限制才 3,这里就要遇到本题真正的看点:一段接不完,得想办法续。
取 c · 算这一段能连放几个：轮到 c。一段最多连放 3 个,而 c 有 4 个,取小的,这一段先放 3 个 c。放的时候盯着:一旦连续凑满 3 个,就不能再直接接第 4 个 c 了。先把这 3 个 c 填进接下来的三个空位。
放第 1 个 c → 位置 2：第一个 c 落到位置 2,c 的剩余从 4 减到 3。当前这段连续 c 的长度是 1。这一位为什么不接着放 z?因为 z 已经没有了,c 是现在能拿到的最大字母,放 c 就是这一位的最优选择。
放第 2 个 c → 位置 3：第二个 c 落到位置 3,c 剩余减到 2。绿色的连续 c 段长度变成 2,还没到上限 3,可以再接一个。继续放第三个 c。
放第 3 个 c → 位置 4 · 触及上限：第三个 c 落到位置 4,连续 c 的长度到了 3,正好顶到上限。可 c 还剩 1 个没放。麻烦来了:下一位要是再放 c,连续就变成 4 个,超过限制 3,整串作废。所以这一位绝对不能再接 c。
为什么不能硬接第 4 个 c：设想一下硬接第四个 c:当前这段 c 会连成连续 4 个 c,直接违反至多 3 个的规则,这个串就不合法了。正确做法是先在中间垫一个比 c 小的字母当隔板,把连续的 c 断成两段,之后才能再接 c。下面去找这个隔板。
需要隔板 · 找比 c 小且还有剩的最大字母：隔板不能随便选,为了尽量不拉低字典序,要挑比 c 小的字母里、当前还有剩的、最大的那一个。比 c 小的依次是 b、a。b 一个都没有,跳过;a 还剩 1 个,就用 a 当隔板。挑到了。
选中隔板 a：词频桶里 b 是 0,直接跳过;a 是 1,选中它。这里只放 1 个 a 就够了,隔板的作用是断开连续,用一个就能把前面的 c 段和后面要接的 c 段隔开,多放 a 反而挤占了后面本可以放 c 的位置,不划算。
放隔板 a → 位置 5 · a 用光：把 a 放到位置 5,a 的剩余减到 0,用光了。现在答案末尾是 a,已经不是 c 了,连续的 c 被成功断开。绿色的当前段只剩这一个 a。隔板铺好,可以回头继续处理还剩 1 个的 c 了。
隔板生效 · 末尾变 a,可以再接 c：关键就在这一下:末尾变成了 a,再往后放 c,这个 c 前面紧挨的是 a 而不是 c,连续计数重新从 1 开始,不会触犯规则。隔板的价值就是这个断点。回到 c,看它还剩多少、这一段能放几个。
回到 c · 算这一段能连放几个：继续处理 c。它现在只剩 1 个,一段最多能放 3 个,取小的,这一段就放 1 个 c。放完 c 也就用光了。填到最后一个空位。
放最后 1 个 c → 位置 6 · c 用光：最后一个 c 落到位置 6,c 的剩余减到 0,也用光了。这一位的 c 紧挨着前面的 a,是新一段连续,长度只有 1,合法。七个位置全部填满,答案已经成形。
所有字母用光 · 构造结束：再看词频桶,z、c、a 的剩余全是 0,没有字母可放了,构造到此结束。七个位置从左到右读出来就是 zzcccac。因为每一步都在最靠前的位置放了当前能放的最大字母,整串的字典序就是最大的。
回放校验 · 每段连续都不超过 3：回放一遍最终串 zzcccac。逐段数连续长度:开头 z z 是 2,接着 c c c 是 3,然后 a 是 1,最后 c 是 1,每一段都不超过限制 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 repeatLimitedString(self, s: str, repeatLimit: int) -> str: cnt = [0] * 26 for c in s: cnt[ord(c) - ord("a")] += 1 ans = [] j = 24 for i in range(25, -1, -1): j = min(i - 1, j) while 1: x = min(repeatLimit, cnt[i]) cnt[i] -= x ans.append(ascii_lowercase[i] * x) if cnt[i] == 0: break while j >= 0 and cnt[j] == 0: j -= 1 if j < 0: break cnt[j] -= 1 ans.append(ascii_lowercase[j]) return "".join(ans)复杂度
- 时间：O(n + 26)，n 是 s 的长度。统计词频扫一遍 s 是 O(n);主体里下标 i 从 25 到 0 单调递减、隔板指针 j 也只会单调下降,两个指针各自最多走 26 步,放字符的总次数不超过 n。合起来是线性的 O(n),字母集大小 26 是常数
- 空间：O(26)，按峰值算。只用了一个长度 26 的计数数组和两个指针,与 n 无关,是常数级。答案串不计入额外空间
易错点
面试追问把动画讲成自己的话
追问这题的贪心策略一句话怎么说?
追问为什么这样贪心是对的,不会错过更大的解?
追问找隔板那个指针为什么可以只往一个方向走?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
雇佣 K 位工人的总代价
LeetCode 2462 · 中等 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题