难度: Medium
给定两个整数 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 <= 100a 和 b，保证存在满足要求的 s 运行时间: 25 ms
内存: 16.0 MB
class Solution:
def strWithout3a3b(self, a: int, b: int) -> str:
result = ""
while a > 0 or b > 0:
# 确保字符串末尾不是'aaa'或'bbb'
if len(result) >= 2 and result[-1] == result[-2] == 'a':
result += 'b'
b -= 1
elif len(result) >= 2 and result[-1] == result[-2] == 'b':
result += 'a'
a -= 1
# 优先添加剩余数量较多的字符
elif a >= b:
result += 'a'
a -= 1
else:
result += 'b'
b -= 1
return result
该题解采用的是贪心算法。首先，根据输入的两个整数a和b，分别代表字符'a'和'b'的数量。解题的核心思路是逐步构建结果字符串，同时确保字符串中不会出现连续三个相同的字符。在构建过程中，我们首先检查字符串末尾是否已经有连续两个相同的字符，若有，则添加另一种字符以打破可能的三连字符。若无连续字符，或者上述条件不满足，则优先添加数量较多的字符，以尽快消耗更多的字符。通过这种方式，我们保证了生成的字符串符合题目要求。
时间复杂度: O(a + b)
空间复杂度: O(a + b)
class Solution:
def strWithout3a3b(self, a: int, b: int) -> str:
result = ''
while a > 0 or b > 0:
# 检查末尾是否有连续两个'a'
if len(result) >= 2 and result[-1] == result[-2] == 'a':
result += 'b' # 添加'b'以避免出现'aaa'
b -= 1
# 检查末尾是否有连续两个'b'
elif len(result) >= 2 and result[-1] == result[-2] == 'b':
result += 'a' # 添加'a'以避免出现'bbb'
a -= 1
# 若没有连续字符问题，优先添加剩余数量较多的字符
elif a >= b:
result += 'a'
a -= 1
else:
result += 'b'
b -= 1
return result
在这种情况下，如果另一种字符的剩余数量为0，则无法添加该字符来阻止形成三连字符。这种情况表明已经无法继续按照题目要求构建字符串而不违反规则（不含连续三个相同字符）。因此，这实际上是一种特殊情况，需要在算法中加以检测。如果发生这种情况，表明无法生成符合条件的字符串，应当返回一个错误或特殊值，例如返回一个空字符串或者特定的错误信息，表示无法构造符合条件的输出。
贪心算法在这个问题中通过每次选择尽可能延长而不违反规则的字符串来确保局部最优。选择添加字符的逻辑是，如果已经存在两个连续相同字符，则添加另一种字符，防止出现三个连续相同字符；如果没有连续字符问题，则优先添加剩余数量较多的字符。这种方法通常可以防止立即违反条件，但确实存在特殊场景，如上一问题所述，若剩余字符不足以防止三连，可能导致无解的情况。因此，贪心算法确保了在大多数情况下的有效构建，但需要额外的逻辑来处理特殊或极端情况。
在字符数量相等时优先添加'a'的策略是为了简化决策过程。实际上，如果'a'和'b'的数量差异很大，这种偏向可能不是最优的选择。例如，如果'b'的数量远多于'a'，则持续优先添加'a'可能会在剩余很多'b'时用完'a'，导致无法有效平衡剩余字符。在这种情况下，更合理的策略可能是根据剩余的数量比例来决定添加哪个字符，以更好地保持字符的平衡，避免出现无法添加足够的字符来打破连续性的情况。因此，算法在处理极端差异大的输入时可能需要调整以适应不同的情况。