How does the greedy approach work in this problem?

The greedy approach ensures that, at each step, the character with the larger remaining count is chosen, but no more than two consecutive characters of the same type are appended.

Why is it important to check the last two characters of the string?

Checking the last two characters ensures that the string does not contain any consecutive sequences of 'AAA' or 'BBB', which is prohibited in the problem constraints.

What happens if I append too many of the same character?

Appending too many of the same character will violate the problem's constraint, resulting in an invalid string that contains either 'AAA' or 'BBB'.

How can I handle edge cases where a or b is zero?

If either a or b is zero, the solution is trivial—simply return a string composed entirely of the other character, which is valid as long as it's within the problem constraints.

How does GhostInterview help with solving this problem?

GhostInterview provides step-by-step guidance on applying the greedy algorithm, ensuring the string construction avoids invalid subsequences and helps optimize the solution.

#984

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

不含 AAA 或 BBB 的字符串

给定两个整数 a 和 b ，返回任意字符串 s ，要求满足： s 的长度为 a + b ，且正好包含 a 个 'a' 字母与 b 个 'b' 字母；子串 'aaa' 没有出现在 s 中；子串 'bbb' 没有出现在 s 中。示例 1：输入： a = 1, b = 2 输出： "abb" …

字符串贪心

题目描述

给定两个整数 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

lightbulb

解题思路

方法一：贪心 + 构造

循环构造字符串，当 $a$ 和 $b$ 都大于 0 时：

如果 $a\gt b$ ，添加字符串 "aab"
如果 $b\gt a$ ，添加字符串 "bba"
如果 $a=b$ ，添加字符串 "ab"

循环结束，若 $a$ 有剩余，则添加 $a$ 个字符串 "a"；若 $b$ 有剩余，则添加 $b$ 个字符串 "b"。

时间复杂度 $O(a+b)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        ans = []
        while a and b:
            if a > b:
                ans.append('aab')
                a, b = a - 2, b - 1
            elif a < b:
                ans.append('bba')
                a, b = a - 1, b - 2
            else:
                ans.append('ab')
                a, b = a - 1, b - 1
        if a:
            ans.append('a' * a)
        if b:
            ans.append('b' * b)
        return ''.join(ans)

speed

复杂度分析

指标	值
时间	complexity is O(A + B) where A and B are the counts of 'a' and 'b', as we process each character once. Space complexity is O(A + B) since we need to store the resulting string, which will have a total length of A + B.
空间	O(A+B)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of the greedy choice by selecting characters based on the remaining count while avoiding invalid sequences.
question_mark
The candidate correctly applies the invariant check to ensure no invalid subsequences are formed.
question_mark
The candidate shows efficiency in constructing the string without unnecessary operations or backtracking.

warning

常见陷阱

外企场景

error
Failing to implement the invariant check properly, leading to invalid strings.
error
Greedily appending too many of the same character, creating an invalid subsequence.
error
Overcomplicating the solution by considering unnecessary operations, when the problem can be solved by a simple greedy approach.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The number of 'a's and 'b's can be arbitrary within the constraint bounds, testing the generality of the greedy approach.
arrow_right_alt
Handling very large inputs (A and B up to 100) tests the candidate's ability to construct the string efficiently.
arrow_right_alt
Edge cases where one of A or B is zero, testing if the string can be formed with only one character type.

help

常见问题

外企场景

继续练习

#955 删列造序 II #942 增减字符串匹配 #936 戳印序列