README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/0900-0999/0984.String%20Without%20AAA%20or%20BBB/README.md	贪心 字符串

984. 不含 AAA 或 BBB 的字符串

English Version

题目描述

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

​​​

解法

方法一：贪心 + 构造

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

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

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

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

Python3

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)

Java

class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuilder ans = new StringBuilder();
        while (a > 0 && b > 0) {
            if (a > b) {
                ans.append("aab");
                a -= 2;
                b -= 1;
            } else if (a < b) {
                ans.append("bba");
                a -= 1;
                b -= 2;
            } else {
                ans.append("ab");
                --a;
                --b;
            }
        }
        if (a > 0) {
            ans.append("a".repeat(a));
        }
        if (b > 0) {
            ans.append("b".repeat(b));
        }
        return ans.toString();
    }
}

C++

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

Go

func strWithout3a3b(a int, b int) string {
	var ans strings.Builder
	for a > 0 && b > 0 {
		if a > b {
			ans.WriteString("aab")
			a -= 2
			b -= 1
		} else if a < b {
			ans.WriteString("bba")
			a -= 1
			b -= 2
		} else {
			ans.WriteString("ab")
			a--
			b--
		}
	}
	if a > 0 {
		ans.WriteString(strings.Repeat("a", a))
	}
	if b > 0 {
		ans.WriteString(strings.Repeat("b", b))
	}
	return ans.String()
}