原文链接: https://leetcode-cn.com/problems/string-without-aaa-or-bbb

英文原文

Given two integers a and b, return any string s such that:

• s has length a + b and contains exactly a 'a' letters, and exactly b 'b' letters,
• The substring 'aaa' does not occur in s, and
• The substring 'bbb' does not occur in s.

 

Example 1:

Input: a = 1, b = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.

Example 2:

Input: a = 4, b = 1
Output: "aabaa"

 

Constraints:

• 0 <= a, b <= 100
• It is guaranteed such an s exists for the given a and b.

中文题目

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

 

提示：

1. 0 <= A <= 100
2. 0 <= B <= 100
3. 对于给定的 A 和 B，保证存在满足要求的 S。

通过代码

官方题解

方法：贪心

思路

直观感觉，我们应该先选择当前所剩最多的待写字母写入字符串中。举一个例子，如果 A = 6, B = 2，那么我们期望写出 'aabaabaa'。进一步说，设当前所剩最多的待写字母为 x，只有前两个已经写下的字母都是 x 的时候，下一个写入字符串中的字母才不应该选择它。

算法

我们定义 A, B：待写的 'a' 与 'b' 的数量。

设当前还需要写入字符串的 'a' 与 'b' 中较多的那一个为 x，如果我们已经连续写了两个 x 了，下一次我们应该写另一个字母。否则，我们应该继续写 x。

[xe7TWkmP-Java]
class Solution {
    public String strWithout3a3b(int A, int B) {
        StringBuilder ans = new StringBuilder();

        while (A > 0 || B > 0) {
            boolean writeA = false;
            int L = ans.length();
            if (L >= 2 && ans.charAt(L-1) == ans.charAt(L-2)) {
                if (ans.charAt(L-1) == 'b')
                    writeA = true;
            } else {
                if (A >= B)
                    writeA = true;
            }

            if (writeA) {
                A--;
                ans.append('a');
            } else {
                B--;
                ans.append('b');
            }
        }

        return ans.toString();
    }
}

[xe7TWkmP-Python]
class Solution(object):
    def strWithout3a3b(self, A, B):
        ans = []

        while A or B:
            if len(ans) >= 2 and ans[-1] == ans[-2]:
                writeA = ans[-1] == 'b'
            else:
                writeA = A >= B

            if writeA:
                A -= 1
                ans.append('a')
            else:
                B -= 1
                ans.append('b')

        return "".join(ans)

复杂度分析

• 时间复杂度：$O(A+B)$。

• 空间复杂度：$O(A+B)$。

统计信息

通过次数	提交次数	AC比率
9415	22442	42.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言