0984. 不含 AAA 或 BBB 的字符串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

给定两个整数 a 和 b，返回任意字符串 s，要求满足：

• s 的长度为 a + b，且正好包含 a 个 'a' 字母与 b 个 'b' 字母
• 子串 'aaa' 没有出现在 s 中
• 子串 'bbb' 没有出现在 s 中

---

示例 1：

输入：a = 1, b = 2
输出："abb"

解释：
"abb", "bab" 和 "bba" 都是正确答案。

---

示例 2：

输入：a = 4, b = 1
输出："aabaa"

---

提示：

• 0 <= a, b <= 100
• 对于给定的 a 和 b，保证存在满足要求的 s

2. 🎯 s.1 - 贪心

js

/**
 * @param {number} a
 * @param {number} b
 * @return {string}
 */
var strWithout3a3b = function (a, b) {
  let result = ''

  while (a > 0 || b > 0) {
    const len = result.length
    // 检查最后两个字符是否相同
    const lastTwo = len >= 2 && result[len - 1] === result[len - 2]

    // 决定写入哪个字符
    let writeA = false
    if (lastTwo) {
      // 如果最后两个字符相同，必须写入另一个字符
      writeA = result[len - 1] === 'b'
    } else {
      // 选择剩余数量更多的字符
      writeA = a >= b
    }

    if (writeA) {
      // 如果 a 剩余数量远大于 b，可以连续写两个 'a'
      if (a >= 2 && a >= b + 2) {
        result += 'aa'
        a -= 2
      } else {
        result += 'a'
        a--
      }
    } else {
      // 如果 b 剩余数量远大于 a，可以连续写两个 'b'
      if (b >= 2 && b >= a + 2) {
        result += 'bb'
        b -= 2
      } else {
        result += 'b'
        b--
      }
    }
  }

  return result
}

• 时间复杂度：$O(a+b)$，需要构造长度为 a+b 的字符串
• 空间复杂度：$O(1)$，不计入结果字符串的空间开销

算法思路：

• 贪心策略：每次优先选择剩余数量更多的字符，这样可以更好地平衡字符分布
• 避免连续三个：检查最后两个字符，如果相同则必须写入另一个字符
• 连续写两个：当某个字符剩余数量远大于另一个（差值 ≥ 2）时，可以连续写两个该字符加快消耗
• 单个写入：否则每次只写一个字符，逐步减少剩余数量
• 循环终止：当两个字符都用完时结束