文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题不含 AAA 或 BBB 的字符串出处984. 不含 AAA 或 BBB 的字符串难度4 级题目描述要求给定两个整数a \texttt{a}a和b \texttt{b}b返回任意满足以下要求的字符串s \texttt{s}ss \texttt{s}s的长度为a b \texttt{a} \texttt{b}ab且正好包含a \texttt{a}a个字母‘a’ \texttt{a}‘a’与b \texttt{b}b个字母‘b’ \texttt{b}‘b’。子串aaa \texttt{aaa}aaa没有出现在s \texttt{s}s中。子串bbb \texttt{bbb}bbb没有出现在s \texttt{s}s中。示例示例 1输入a 1, b 2 \texttt{a 1, b 2}a 1, b 2输出abb \texttt{abb}abb解释abb \texttt{abb}abb、bab \texttt{bab}bab和bba \texttt{bba}bba都是正确答案。示例 2输入a 4, b 1 \texttt{a 4, b 1}a 4, b 1输出aabaa \texttt{aabaa}aabaa数据范围0 ≤ a, b ≤ 100 \texttt{0} \le \texttt{a, b} \le \texttt{100}0≤a, b≤100对于给定的a \texttt{a}a和b \texttt{b}b保证存在满足要求的s \texttt{s}s解法思路和算法这道题要求构造字符串s ss满足由a aa个字母‘a’ \text{a}‘a’和b bb个字母‘b’ \text{b}‘b’组成且不存在三个相同的连续字母因此相同字母最多连续出现两次。在b bb的值确定的情况下a aa的值最大时对应的s ss由b bb组“aab \text{aab}“aab以及一组“aa \text{aa}“aa构成此时s ss的长度是a b 3 b 2 a b 3b 2ab3b2因此a 2 b 2 a 2b 2a2b2。当b 0 b 0b0时也适用。同理可知在a aa的值确定的情况下b bb的最大值是2 a 2 2a 22a2。因此非负整数a aa和b bb满足0 ≤ a ≤ 2 b 2 0 \le a \le 2b 20≤a≤2b2和0 ≤ b ≤ 2 a 2 0 \le b \le 2a 20≤b≤2a2。当a b a bab时用x xx表示每个字母的出现次数则s ss可以由x xx组“ab \text{ab}“ab构成此时s ss中的任意两个相邻字母都不相同。当a ≠ b a \ne bab时出现次数较多的字母将在s ss中连续出现构造时应满足相同字母最多连续出现两次。以下考虑a b a bab的情况对于a b a bab的情况做法相同只要将两个字母交换即可。当a b 0 a b 0ab0时每次将一组“aab \text{aab}“aab拼接到s ss的末尾则每次使用两个‘a’ \text{a}‘a’和一个‘b’ \text{b}‘b’因此将a aa的值减2 22将b bb的值减1 11此时s ss中不存在三个相同的连续字母。重复该操作直到a b a bab或b 0 b 0b0。如果a b a bab则每次将一组“ab \text{ab}“ab拼接到s ss的末尾每次使用一个‘a’ \text{a}‘a’和一个‘b’ \text{b}‘b’因此将a aa的值减1 11将b bb的值减1 11此时s ss中不存在三个相同的连续字母。重复该操作直到a b 0 a b 0ab0。如果a 0 a 0a0且b 0 b 0b0则将剩余的‘a’ \text{a}‘a’拼接到s ss的末尾。上述做法使用贪心策略贪心策略的正确性说明如下。当a b 0 a b 0ab0时每次将一组“aab \text{aab}“aab拼接到s ss的末尾因此s ss为空或者s ss的最后一个字母是‘b’ \text{b}‘b’。由于每一次拼接的两个或三个字母都以‘a’ \text{a}‘a’开始且最多有两个连续的‘a’ \text{a}‘a’因此不会出现三个相同的连续字母。由于保证存在满足要求的s ss因此当a 0 a 0a0且b 0 b 0b0时必有a ≤ 2 a \le 2a≤2此时s ss为空或者s ss的最后一个字母是‘b’ \text{b}‘b’将剩余的‘a’ \text{a}‘a’拼接到s ss的末尾不会出现三个相同的连续字母。代码classSolution{publicStringstrWithout3a3b(inta,intb){StringBuffersbnewStringBuffer();while(abb0){sb.append(aab);a-2;b--;}while(baa0){sb.append(bba);b-2;a--;}while(a0b0){sb.append(ab);a--;b--;}while(a0){sb.append(a);a--;}while(b0){sb.append(b);b--;}returnsb.toString();}}复杂度分析时间复杂度O ( a b ) O(a b)O(ab)其中a aa和b bb分别是s ss中的字母‘a’ \text{a}‘a’和字母‘b’ \text{b}‘b’的个数。需要构造长度为a b a bab的字符串拼接每个字母的时间是O ( 1 ) O(1)O(1)。空间复杂度O ( a b ) O(a b)O(ab)其中a aa和b bb分别是s ss中的字母‘a’ \text{a}‘a’和字母‘b’ \text{b}‘b’的个数。需要创建一个长度为a b a bab的StringBuffer \texttt{StringBuffer}StringBuffer或StringBuilder \texttt{StringBuilder}StringBuilder类型的对象。由于 Java 中的String \texttt{String}String类型的对象不可变因此空间复杂度至少为O ( a b ) O(a b)O(ab)。