LeetCode 984 String Without AAA or BBB

LeetCode

<div>

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:

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

Example 2:

<pre>Input: a = 4, b = 1 Output: "aabaa" </pre>

Constraints:

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

</div>

题目大意：

给定两个整数代表ab的个数，生成一个字符串，字符串ab频数不能超过这2个数，不能有连续的aaa, bbb, 求此种字符串的最大长度

解题思路：

参考LeetCode 1405 Longest Happy String, 此题不用heap因为只有两种字符

解题步骤：

N/A

注意事项：

1. 不能连续的处理

Python代码：

def strWithout3a3b(self, a: int, b: int) -> str:
	res = ''
	while a > 0 or b > 0:
		if a > b:
			if len(res) > 1 and res[-2] == res[-1] == 'a':
				res += 'b'
				b -= 1
			else:
				res += 'a'
				a -= 1
		else:
			if len(res) > 1 and res[-2] == res[-1] == 'b':
				res += 'a'
				a -= 1
			else:
				res += 'b'
				b -= 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)