构造最长的新字符串

难度: Medium

给你三个整数 x ，y 和 z 。

这三个整数表示你有 x 个 "AA" 字符串，y 个 "BB" 字符串，和 z 个 "AB" 字符串。你需要选择这些字符串中的部分字符串（可以全部选择也可以一个都不选择），将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串 "AAA" 或者 "BBB" 。

请你返回 新字符串的最大可能长度。

子字符串 是一个字符串中一段连续非空的字符序列。

示例 1：

输入：x = 2, y = 5, z = 1
输出：12
解释： 我们可以按顺序连接 "BB" ，"AA" ，"BB" ，"AA" ，"BB" 和 "AB" ，得到新字符串 "BBAABBAABBAB" 。
字符串长度为 12 ，无法得到一个更长的符合题目要求的字符串。

示例 2：

输入：x = 3, y = 2, z = 2
输出：14
解释：我们可以按顺序连接 "AB" ，"AB" ，"AA" ，"BB" ，"AA" ，"BB" 和 "AA" ，得到新字符串 "ABABAABBAABBAA" 。
字符串长度为 14 ，无法得到一个更长的符合题目要求的字符串。

提示：

1 <= x, y, z <= 50

Submission

运行时间: 29 ms

内存: 16.0 MB

class Solution:
    def longestString(self, x: int, y: int, z: int) -> int:
        return (min(x, y) * 2 + (x != y) + z) * 2

Explain

这个题解首先利用了贪心策略来最大化生成字符串的长度。主要思路是：1. 尽可能多地使用'AB'字符串，因为它可以在不违背规则的情况下插入在'AA'和'BB'之间。2. 当'AB'用尽后，根据'AA'和'BB'的数量，交替放置'AA'和'BB'直到其中一种用完。3. 如果'AA'和'BB'数量不相等，那么在数量较多的那种字符后再添加一个相同的字符，但不能超过两个连续的相同字符。计算方法中，min(x, y) * 2计算了可以安全交替放置的'AA'和'BB'的总数量，(x != y)用于检查'AA'和'BB'的数量是否不相同，如果不相同，那么可以额外再放置一个字符，z * 2计算了可以由'AB'提供的字符数。

时间复杂度: O(1)

空间复杂度: O(1)

# 定义解决问题的函数

class Solution:
    def longestString(self, x: int, y: int, z: int) -> int:
        # 计算可以安全交替放置'AA'和'BB'的字符总数
        # min(x, y) * 2 计算交替放置'AA'和'BB'所能达到的最大长度
        # (x != y) 检查'AA'和'BB'数量是否不等，如果不等，可以额外放置一个'AA'或'BB'
        # z * 2 计算'AB'贡献的字符数
        return (min(x, y) * 2 + (x != y) + z) * 2

Explore

在使用'AB'字符串后，可以通过交替放置'AA'和'BB'来避免形成'AAA'或'BBB'。例如，如果你有剩余的'AA'和'BB'，可以按照'AA-BB-AA-BB'的顺序排列。如果'AB'用尽后仍有剩余的'AA'或'BB'，可以确保不会连续使用超过两个相同的字符串块，如使用'AA'后，必须尝试插入'BB'（如果还有剩余），以此保证不会违反规则。

逻辑`(x != y)`用来增加一个字符长度的处理不一定在所有情况下都正确。特别是如果其中一个值（x或y）为0时，就不能再添加任何额外的'AA'或'BB'，因为这将导致形成'AAA'或'BBB'。因此，应该在两者都大于0的情况下才考虑增加一个字符，以确保可以安全地添加而不违反连续性规则。

是的，公式中的乘以2是因为每个字符串单元('AA', 'BB', 'AB')都包含两个字符。因此，不论是'AA', 'BB'还是'AB'，每次计数实际上都代表了两个字符。这就是为什么最终结果需要乘以2，以确保返回的是字符的总数而非字符串块的数量。