题目描述
给你三个整数 x
,y
和 z
。
这三个整数表示你有 x
个 "AA"
字符串,y
个 "BB"
字符串,和 z
个 "AB"
字符串。你需要选择这些字符串中的部分字符串(可以全部选择也可以一个都不选择),将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串 "AAA"
或者 "BBB"
。
请你返回新字符串的最大可能长度。
子字符串 是一个字符串中一段连续 非空 的字符序列。
样例
输入:x = 2, y = 5, z = 1
输出:12
解释: 我们可以按顺序连接 "BB","AA","BB","AA","BB" 和 "AB",
得到新字符串 "BBAABBAABBAB"。
字符串长度为 12,无法得到一个更长的符合题目要求的字符串。
输入:x = 3, y = 2, z = 2
输出:14
解释:我们可以按顺序连接 "AB","AB","AA","BB","AA","BB" 和 "AA",
得到新字符串 "ABABAABBAABBAA"。
字符串长度为 14,无法得到一个更长的符合题目要求的字符串。
限制
1 <= x, y, z <= 50
算法
(思维题) $O(1)$
- 如果
AA
和BB
的个数最多只相差 $1$,则可以让AA
和BB
间隔排列,然后AB
以连续的方式接到开头或者末尾,所以这种情况全部字符串都可以用到。 - 如果个数相差超过了 $1$,则超出的
AA
或BB
也不能让AB
进来间隔排列,即AA AB AA
或BB AB BB
都是不可行的,所以这种情况,只有 $2\min(x, y) + 1 + z$ 个字符串可以用到。
时间复杂度
- 分两种情况讨论,时间复杂度为 $O(1)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int longestString(int x, int y, int z) {
if (abs(x - y) <= 1)
return (x + y + z) * 2;
return (2 * min(x, y) + 1 + z) * 2;
}
};