题目描述

给定两个整数 A 和 B，返回任意一个字符串 S 使得：

• S 的长度为 A + B，包含 A 个 'a' 和 B 个 'b'；
• 子串 'aaa' 不能在 S 中出现；
• 子串 'bbb' 不能在 S 中出现；

样例

输入：A = 1, B = 2
输出："abb"
解释"abb", "bab" 和 "bba" 都是正确答案。

输入：A = 4, B = 1
输出："aabaa"

注意

• 0 <= A <= 100
• 0 <= B <= 100
• 在给定 A 和 B 下，保证 S 存在。

算法1

(构造) $O(n + m)$

1. 我们同时考虑 A 和 B。
2. 如果 A 大于 B，则我们每一次写 2 个 a，然后写 1 个 b（如果还能写），直到它们个数相等，每次写一对 ab。
3. 反之，如果 B 大于 A，则我们每一次写 2 个 b，然后写 1 个 a（如果还能写），直到它们个数相等，然后每次写一对 ab。

时间复杂度

• 最多构造 $n + m$ 个字母，故时间复杂度为 $O(n + m)$。

空间复杂度

• 答案存储需要 $O(n + m)$ 的空间。

C++ 代码

class Solution {
public:
    string strWithout3a3b(int A, int B) {
        string ans;
        while (A > 0 || B > 0) {
            if (A > B) {
                ans += "a";
                A--;
                if (A > 0) {
                    ans += "a";
                    A--;
                }
                if (B > 0) {
                    ans += "b";
                    B--;
                }
            }
            else if (A < B) {
                ans += "b";
                B--;
                if (B > 0) {
                    ans += "b";
                    B--;
                }
                if (A > 0) {
                    ans += "a";
                    A--;
                }
            }
            else {
                ans += "ab";
                A--;
                B--;
            }
        }
        return ans;
    }
};

算法2

(构造) $O(n + m)$

1. 首先，按 A 和 B 的最小值，以 ab 的形式构造出字符串。
2. 如果此时 A 和 B 相等，则直接返回。
3. 否则，如果 A 大于 B，则从开始位置添加 a，即在原串中每隔两个字母添加 1 个 a。但注意最后可能还需要在最后额外添加两个 a。
4. 如果 B 大于 A，则从开始位置添加 b，即在原串中每隔两个字母添加 1 个 b。但注意最后可能还需要在开头额外添加两个 b。

时间复杂度

• 添加字母的过程可以通过构造新串的方式实现，最多构造 $O(n + m)$ 个字母，故时间复杂度为 $O(n + m)$。

空间复杂度

• 临时字符串和答案存储需要 $O(n + m)$ 的空间。

C++ 代码

class Solution {
public:
    string strWithout3a3b(int A, int B) {
        string s;
        for (int i = 0, j = 0; i < A && j < B; i++, j--)
            s += "ab";

        string ans;
        if (A > B) {
            A -= B;
            int j = 0;
            while (A > 0 && j < 2 * B) {
                ans += 'a';
                ans += s[j];
                ans += s[j + 1];
                A--;
                j += 2;
            }
            while (j < 2 * B) {
                ans += s[j];
                j++;
            }
            while (A--)
                ans += 'a';
        }
        else if (A < B) {
            B -= A;
            int j = 0;
            while (B > 0 && j < 2 * A) {
                ans += s[j];
                ans += s[j + 1];
                ans += 'b';
                B--;
                j += 2;
            }
            while (j < 2 * A) {
                ans += s[j];
                j++;
            }
            if (B == 1)
                ans = "b" + ans;
            else if (B == 2)
                ans = "bb" + ans;
        }
        else
            ans = s;

        return ans;
    }
};