[LeetCode] 984. String Without AAA or BBB

[grandyang]

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，让返回一个长度为 a+b 的字符串，且只由字符a和b组成，要求不能有三个连着的a或b出现，题目说了对于给定的a和b，一定会有正确的解，让返回一种正确的形式就可以了。题目中给了两个例子来帮助理解，可以发现，a和b的大小关系并不确定，无非也就三种，大于等于和小于，最简单的是相等的时候，直接交替排列即可，虽说可能也存在其他合理的排法，但是没有必要，只要返回的是合理的就行了。接下来就要看不等的情况，比较极端的情况就是a和b中有一个为0，这样直接返回另一个字符组成的字符串就行了，另一个字符的个数也不会超过两个，因为题目中限定了一定有合理的解。如果a和b都不为0，且不等的时候怎么办，比如a大于b时，那么此时可以用两个a，加一个b，尽量让a和b往相等的方向靠拢，则此时对 a-2 和 b-1 调用递归即可，同理，若b大于a，那么此时可以用两个b，加一个a，也尽量让a和b往相等的方向靠拢，则此时对 a-1 和 b-2 调用递归即可，参见代码如下：

解法一：

class Solution {
public:
    string strWithout3a3b(int a, int b) {
        if (a == 0) return string(b, 'b');
        if (b == 0) return string(a, 'a');
        if (a == b) return "ab" + strWithout3a3b(a - 1, b - 1);
        if (a > b) return "aab" + strWithout3a3b(a - 2, b - 1);
        return "bba" + strWithout3a3b(a - 1, b - 2);
    }
};

当然不想用递归也行，迭代的解法稍微长一些，用个 while 循环，只要a和b中有一个为0了就停止，若a大于b，加上 aab，然后a自减1，若b大于a，则加上 bba，然后b自减1，若a和b相等，则加上 ab，之后a和b分别均减1。循环退出后，若a和b还有值，还得加到结果 res，参见代码如下：

解法二：

class Solution {
public:
    string strWithout3a3b(int a, int b) {
        string res;
        while (a && b) {
            if (a > b) {
                res += "aab";
                --a;
            } else if (b > a) {
                res += "bba";
                --b;
            } else {
                res += "ab";
            }
            --a; --b;
        }
        res += string(a, 'a');
        res += string(b, 'b');
        return res;
    }
};

Github 同步地址:

#984

参考资料：

https://leetcode.com/problems/string-without-aaa-or-bbb/

https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/226740/Clean-C%2B%2Bpython-solution

https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/227038/C%2B%2B-short-and-simple-solution

https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/226649/JavaC%2B%2B-(and-Python)-simple-greedy

LeetCode All in One 题目讲解汇总(持续更新中...)