LeetCode 984. 不含 AAA 或 BBB 的字符串
目录
题目描述
题意分析
要构造一个字符串，其中恰好含有 a 个字符
a和 b 个字符b，且不出现连续三个相同字符（既不能有aaa也不能有bbb）。答案不唯一，返回任意一个合法解即可。「恰好」这两个字很关键：不是「至多」，两种字符都必须用完，长度固定为 a + b。
约束是 $0 \le a, b \le 100$，并且题目直接保证答案存在。这一句免掉了无解判断，但它同时也是一个隐含的数量关系——如果某一侧比另一侧多太多（大致超过两倍加二），就一定会被迫出现三连，题目已经把这类输入排除了。
规模极小，长度最多 200，所以时间不是考点，考点在于构造策略是否正确、能否说清楚为什么它不会走进死胡同。
边界要覆盖：某一侧为 0（比如 a = 0、b = 2 时答案只能是 "bb"，b = 3 就不可能存在，题目已排除）、两侧相等（可以交替铺开）、以及某一侧恰好是另一侧两倍多一点（每两个多的配一个少的）。
解法：贪心构造
核心思路
最笨的想法是搜索：逐位枚举放
a还是b，非法就回溯。长度 200 时状态空间大得离谱，虽然剪枝后能过，但完全没抓住这道题要考的东西。瓶颈在于「逐位试错」。换个角度看，每一位其实只有两个候选，真正需要判断的只是「这一位该选谁」；如果能找到一个每步都正确、且永远不会让后续陷入死局的选法，就一趟扫描搞定。
观察从最危险的情形入手：什么时候会写出三连？只有当结尾已经是两个相同字符，而下一位又放了同一个字符。所以「结尾两个相同」是一条硬约束——此时下一位没有选择余地，必须放另一种字符。
剩下的情形（结尾两个不同，或者长度不足 2）是自由的，这时该放哪个？直觉是先放剩余数量更多的那一种。理由是：数量多的一方是潜在的麻烦制造者，它越晚消耗、堆在后面的压力越大，最终一定会撞上三连；而优先消耗它，可以让两边的剩余量持续向平衡靠拢，平衡的局面永远是安全的。
把这两条合起来就是整个策略，并且可以总结成一个不变量：每一步做完选择后，已生成的前缀始终合法（无三连），且剩余的 a、b 仍然满足「能构造出合法后缀」的条件。硬约束触发时另一种字符必定还有剩余——因为若它已耗尽，说明之前连续放了两个多数派字符而少数派为 0，这种局面只可能来自题目已排除的无解输入。
实现上不需要真的记录「上一个放了什么、连放了几个」，直接读结果串最后两个字符即可，状态就藏在已生成的答案里。
解题步骤
- 准备一个可追加的结果容器，容量预留 a + b，避免中途扩容。循环条件是
a > 0 || b > 0，两种字符都用完才停，对应题目的「恰好」。- 每轮先给出默认选择：
chooseA = (a >= b)，即优先消耗剩余更多的一方。相等时倒向a只是为了写法确定，倒向b同样正确。- 接着检查硬约束：若结果长度已达 2 且最后两个字符相同，就必须改选另一种。代码里写成
chooseA = (最后一个字符 == 'b')——最后两个都是b时必须放a，最后两个都是a时必须放b，一句话覆盖两种情况。- 硬约束的判断放在默认选择之后，是因为它是覆盖性的：无论默认选了谁，只要结尾出现两个相同字符，结论都被强制改写。顺序反过来写，默认选择就会把强制结果盖掉。
- 按
chooseA追加对应字符，并把相应计数减一。计数和追加必须同步，否则剩余量与已写入内容会脱节。- 循环结束后把容器转成字符串返回。不需要在最后做任何合法性校验，因为每一步都已保证前缀合法。
以
a = 4、b = 1走一遍：初始结果为空。第一轮长度为 0，硬约束不触发，4 >= 1选a，结果 "a"，a 变 3。第二轮长度为 1，仍不足 2，3 >= 1选a，结果 "aa"，a 变 2。第三轮长度为 2 且最后两个都是a，硬约束触发，强制选b，结果 "aab"，b 变 0。第四轮最后两个是a、b不相同，默认2 >= 0选a，结果 "aaba"，a 变 1。第五轮最后两个是b、a不相同，默认1 >= 0选a，结果 "aabaa"，a 变 0。此时 a 和 b 都为 0，循环结束，返回 "aabaa"。检查一下：四个a、一个b数量正确，最长连续同字符是 "aa"，没有三连，合法。
代码实现
class Solution {
// 若结果末尾两个字符已经相同，下一位必须放另一种字符，这是保证合法性的硬约束。
public String strWithout3a3b(int a, int b) {
StringBuilder result = new StringBuilder(a + b);
while (a > 0 || b > 0) {
int length = result.length();
boolean chooseA = a >= b;
if (length >= 2 && result.charAt(length - 1) == result.charAt(length - 2)) {
chooseA = result.charAt(length - 1) == 'b';
}
if (chooseA) {
result.append('a');
a--;
} else {
result.append('b');
b--;
}
}
return result.toString();
}
}
func strWithout3a3b(a int, b int) string {
// 若结果末尾两个字符已经相同，下一位必须放另一种字符，这是保证合法性的硬约束。
result := make([]byte, 0, a+b)
for a > 0 || b > 0 {
length := len(result)
chooseA := a >= b
if length >= 2 && result[length-1] == result[length-2] {
chooseA = result[length-1] == 'b'
}
if chooseA {
result = append(result, 'a')
a--
} else {
result = append(result, 'b')
b--
}
}
return string(result)
}
复杂度分析
- 时间复杂度：$O(a + b)$，每轮循环恰好写出一个字符，循环次数等于结果长度，每轮只做常数次比较。
- 空间复杂度：$O(1)$，不计返回的结果串时只用到两个计数器和两次字符读取；结果串本身是必须的输出，长度为 a + b。
关键点总结
- 构造类题目先找「硬约束」再找「软偏好」：硬约束是不满足就直接非法的规则，必须最后判定且具有覆盖性；软偏好只在自由时生效。这个分层能把大量分支压成两行。
- 「优先消耗剩余更多的一方」是资源分配型贪心的通用直觉，其正确性来自「让剩余量趋于平衡，而平衡局面永远安全」，答题时要把这句理由讲出来，而不是只说「这样比较好」。
- 状态可以藏在已生成的答案里：直接读结果串末尾两个字符，比另外维护「上一个字符是什么、连续了几次」更少出错，也少两个需要同步的变量。
- 题目写「保证答案存在」时，要能主动说出这个保证等价于什么数量关系（多的一方不超过少的一方的两倍加二），否则面试官会怀疑你只是在碰运气。
- 面试视角：这题几乎一定会被追问「为什么贪心是对的」和「不加保证时如何判无解」，能答上这两问比写出代码更重要；再追问就是 1405. 最长快乐字符串，那题扩到三种字符且要求最长，用堆维护剩余最多者即可。
易错点总结
- 错误写法：把硬约束判断写在默认选择之前 → a = 4、b = 1 时第三轮本该被强制放
b，却又被后面的a >= b改回a，写出 "aaa"，直接违规。- 错误写法：默认选择写成「优先放剩余更少的一方」 → a = 4、b = 1 时会先放
b用光少数派，之后只剩四个a且无处可插，必然出现 "aaa"。- 错误写法：只判断最后一个字符与待放字符是否相同就切换 → 退化成严格交替，a = 4、b = 1 时最多写出 "abab" 就无字符可交替，剩下的
a放不下，得不到合法解。- 错误写法：循环条件写成
a > 0 && b > 0→ 少数派先用完后循环立刻结束，a = 4、b = 1 时只返回 "aab"，长度不足，没满足「恰好用完」。- 错误写法：判断末尾时不检查长度是否已达 2，直接访问
result[length - 2]→ 结果串还只有 0 或 1 个字符时下标为负，越界。- 错误写法：追加字符后忘记减对应计数，或者减错了那一个 → 循环永远不结束，或者两种字符的数量与题目要求对不上。
- 错误写法：用
String做拼接而不是StringBuilder／字节切片 → 每次拼接都复制整串，长度 200 虽然不至于超时，但读末尾字符和追加都变成 $O(n)$，写法上直接失分。- 错误写法：写完后再补一段「如果发现三连就回头修补」的逻辑 → 修补会破坏前面已经满足的数量约束，且很难证明修补总能成功；正确的做法是让每一步都不产生三连。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 767. 重构字符串 | 中等 | 任意多种字符且要求相邻不同，需先判无解 |
| 1405. 最长快乐字符串 | 中等 | 三种字符且求最长，用堆挑剩余最多者 |
| 621. 任务调度器 | 中等 | 只求总长度，可用最高频任务直接推公式 |