LeetCode 984. 不含 AAA 或 BBB 的字符串

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 快手
标签
字符串 贪心

题目描述

✅ 984. 不含 AAA 或 BBB 的字符串

image-20260928223907463

题意分析

恰好使用给定数量的字符 a 和 b，构造一个不含连续三个相同字符的字符串，返回任意合法结果。连续两个相同字符是允许的，不要求严格交替，也不要求字典序最小。

两类字符都必须全部用完，不能为了避免三连而丢弃剩余字符。题目保证给出的数量存在解；若两种数量都为零，返回空字符串即可。

解法：贪心构造

核心思路

[!blue]

从左到右追加字符，每次只需检查已有结果的最后两位。若两位相同，下一位被强制确定为另一种字符，否则立刻出现三连；如果没有这个限制，就优先使用剩余数量较多的一种，数量相同任选，代码选择 a。

优先使用多的一类，是为了保留较少字符作为隔断。剩余 b 个字母可以分出 b + 1 个位置放 a，每个位置至多两个；若已有后缀是连续 r 个 a，第一个位置已经被占用 r 个，因此剩余数量必须满足 a <= 2b + 2 - r。b 的容量界同理。这里的后缀长度只可能为零、一、二。

自由选择时，设追加前 a >= b，选择一个 a。它的剩余量减一，而尾部对 a 的占用最多增加一，因此不会破坏 a 的容量界。另一类需要满足的新界是 b <= 2(a - 1) + 2 = 2a，由原来的 b <= a 已经保证。选择 b 的情况对称。

强制换类时，原后缀若为两个 b，原容量界为 b <= 2a；追加一个 a 后，剩余 b 的新容量仍是 2(a - 1) + 2 = 2a，没有变小。a 自身的剩余量与允许量同时减少一，也保持可行。若此时没有 a 可用，容量界会要求剩余 b 也为零，循环已经结束，所以不会在有解输入上被迫使用已经耗尽的字符。

两种选择都保持前缀不含三连，并保留完成剩余数量的能力。每轮消费一个字符，直到全部用完，便得到合法结果。

解题步骤

  1. 创建结果缓冲区，循环直到两种剩余数量都为零。
  2. 默认选择剩余数量较多的一种，数量相同时选择 a。
  3. 若结果末尾两个字符相同，覆盖默认选择，强制追加另一种。
  4. 写入所选字符，并只将它的剩余数量减一。
  5. 返回构造出的完整字符串。

代码实现

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(a+b)$，结果缓冲区保存全部输出字符，除此之外只需常数个变量。

关键点总结

[!green]

  • 禁止三连是强制规则，优先多者只能在不冲突时使用。
  • 少的一类是隔断资源，提前适当消耗多者，避免尾部留下无法分隔的一长段。
  • 可行性需要同时考虑剩余数量与已有末尾占用，不能只看两种数量之差。
  • 题目保证初始有解，选择规则继续保持可完成性，直到所有字符消耗完。

易错点总结

[!yellow]

  • 只按数量多者追加，不检查末尾两位，会直接生成三连。
  • 盲目一字一换地交替，可能过早用完少的一类，剩下多的一类无法全部放入。
  • 末尾已经相同两位仍让数量规则优先，忽略了下一位实际上没有选择余地。
  • 为了停止冲突而提前结束，得到的只是合法前缀，没有使用完题目指定数量。
  • 追加一种字符却减少另一种计数，最终字符数量和循环结束条件都会错误。
  • 把当前规则直接套到不保证有解的输入，需要额外判断可行性；本题给定了有解前提。

相似题目

题目 难度 关联与区别
767. 重构字符串 中等 原题禁止两个相同字符相邻，本题允许两个连续但不能三个连续，需要保留最近两位状态。
1405. 最长快乐字符串 中等 原题有三种字符且可舍弃剩余字符，本题两种字符数量固定并要求全部使用。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/25121489
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！