LEETCODE 984. String Without AAA or BBB 解题思路分析

题目大意：

不含 AAA 或 BBB 的字符串

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=984

解题思路分析：

这道题的核心要求是，相同字符不能连续出现2次以上，解题时要分几种情况来考虑，如果A等于B，那么直接abab交叉打印即可。如果A或者B等于0，那么就将不为0的一方都打印出来即可（因为本题保证了一定能打印出满足要求的s，因此不会存在例外情况）。

接下来重点在于，当A和B都大于0，并且数量不同时该如何应对。这里我们可以使用贪心算法，假如A大于B时，我们可以打印两个a和一个b，”aab”，此时A的数量减二，B数量减一。重复此步骤，直到A等于B，或者B数量到0为止。这时可以按照文章上一段的思路继续求解剩余部分。同理，B大于A时也是相同的逻辑。

优化：字符串操作时，使用StringBuilder要比直接字符串相加效率高。

实现代码：

public String strWithout3a3b(int A, int B) {
    // 返回结果
    StringBuilder res= new StringBuilder();
    if(A==B){ // 数量相同时，交叉打印
        for(int i=0;i<A;i++) res.append("ab");
    }else if(A==0){ // A为0时，打印出剩余的所有b
        for(int i=0;i<B;i++) res.append("b");
    }else if(B==0){ // B为0时，打印出剩余的所有a
        for(int i=0;i<A;i++) res.append("a");
    }else if(A>B){ // A大于B时，打印aab
        while(A>B&&A>=2&&B>=1){
            res.append("aab");
            A-=2;
            B-=1;
        }
        // 剩余部分交给子问题处理
        res.append(strWithout3a3b(A,B));
    }else if(B>A){ // B大于A时，打印bba
        while(B>A&&A>=1&&B>=2){
            res.append("bba");
            A-=1;
            B-=2;
        }
        // 剩余部分交给子问题处理
        res.append(strWithout3a3b(A,B));
    }
    return res.toString();
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for String Without AAA or BBB.

Memory Usage: 33.9 MB, less than 100.00% of Java online submissions for String Without AAA or BBB.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-984-string-without-aaa-or-bbb-解题思路分析/