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
解题思路
这道题的关键观察是：所有的 “AB” 都可以被使用，因为它们不会产生连续的三个相同字符。
主要思路如下：
“AB” 的使用策略：所有
z个 “AB” 都能被完全使用。无论字符串以 ‘A’ 还是 ‘B’ 开头，我们都能找到合适的位置插入所有 “AB”。“AA” 和 “BB” 的交替模式：为了避免 “AAA” 或 “BBB”，“AA” 和 “BB” 必须交替出现。有两种基本模式：
- 模式1：AA-BB-AA-BB-…（以 “AA” 开头）
- 模式2：BB-AA-BB-AA-…（以 “BB” 开头）
最优策略分析：
- 如果
x == y，两种模式都能用完所有 “AA” 和 “BB” - 如果
x > y，优选模式1，最多能用min(x, y+1)个 “AA” 和y个 “BB” - 如果
y > x，优选模式2，最多能用x个 “AA” 和min(y, x+1)个 “BB”
- 如果
计算公式：
- 当
|x-y| <= 1时，所有 “AA” 和 “BB” 都能使用 - 否则，较多的那种字符串最多只能比较少的多用一个
- 当
最终答案 = 2 * (使用的AA数量 + 使用的BB数量) + 2 * z
代码实现
class Solution {
public:
int longestString(int x, int y, int z) {
// 所有AB都可以使用
// AA和BB需要交替使用，避免出现AAA或BBB
if (abs(x - y) <= 1) {
// 如果x和y相差不超过1，可以完全交替使用
return 2 * (x + y + z);
} else {
// 较多的那个最多比较少的多用一个
return 2 * (2 * min(x, y) + 1 + z);
}
}
};
class Solution:
def longestString(self, x: int, y: int, z: int) -> int:
# 所有AB都可以使用
# AA和BB需要交替使用，避免出现AAA或BBB
if abs(x - y) <= 1:
# 如果x和y相差不超过1，可以完全交替使用
return 2 * (x + y + z)
else:
# 较多的那个最多比较少的多用一个
return 2 * (2 * min(x, y) + 1 + z)
public class Solution {
public int LongestString(int x, int y, int z) {
// 所有AB都可以使用
// AA和BB需要交替使用，避免出现AAA或BBB
if (Math.Abs(x - y) <= 1) {
// 如果x和y相差不超过1，可以完全交替使用
return 2 * (x + y + z);
} else {
// 较多的那个最多比较少的多用一个
return 2 * (2 * Math.Min(x, y) + 1 + z);
}
}
}
/**
* @param {number} x
* @param {number} y
* @param {number} z
* @return {number}
*/
var longestString = function(x, y, z) {
// 所有AB都可以使用
// AA和BB需要交替使用，避免出现AAA或BBB
if (Math.abs(x - y) <= 1) {
// 如果x和y相差不超过1，可以完全交替使用
return 2 * (x + y + z);
} else {
// 较多的那个最多比较少的多用一个
return 2 * (2 * Math.min(x, y) + 1 + z);
}
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(1) |
| 空间复杂度 | O(1) |