class Solution {
public:
int longestString(int x, int y, int z) {
}
};
6895. 构造最长的新字符串
给你三个整数 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原站题解
python3 解法, 执行用时: 220 ms, 内存消耗: 73 MB, 提交时间: 2023-06-25 09:32:17
@cache
def dfs(x: int, y: int, z: int, k: int) -> int:
if k == 0:
return dfs(x, y - 1, z, 1) + 2 if y else 0
res1 = dfs(x - 1, y, z, 0) + 2 if x else 0
res2 = dfs(x, y, z - 1, 2) + 2 if z else 0
return max(res1, res2)
class Solution:
def longestString(self, x: int, y: int, z: int) -> int:
return max(dfs(x, y, z, 0), dfs(x, y, z, 1))
golang 解法, 执行用时: 268 ms, 内存消耗: 8.2 MB, 提交时间: 2023-06-25 09:31:53
func longestString(x, y, z int) int {
memo := make([][][][3]int, x+1)
for i := range memo {
memo[i] = make([][][3]int, y+1)
for j := range memo[i] {
memo[i][j] = make([][3]int, z+1)
for k := range memo[i][j] {
memo[i][j][k] = [3]int{-1, -1, -1}
}
}
}
// x,y,z代表AA/BB/AB剩余数量，k=0,1,2表示上一个字符串是AA/BB/AB
var dfs func(x, y, z, k int) int
dfs = func(x, y, z, k int) (res int) {
p := &memo[x][y][z][k]
if *p != -1 { // 之前算过
return *p
}
if k == 0 {
if y > 0 {
res = dfs(x, y-1, z, 1) + 2
}
} else {
if x > 0 {
res = dfs(x-1, y, z, 0) + 2
}
if z > 0 {
res = max(res, dfs(x, y, z-1, 2)+2)
}
}
*p = res // 记忆化
return
}
return max(dfs(x, y, z, 0), dfs(x, y, z, 1))
}
func max(a, b int) int { if b > a { return b }; return a }
golang 解法, 执行用时: 0 ms, 内存消耗: 2.8 MB, 提交时间: 2023-06-25 09:30:35
func longestString(x, y, z int) int {
ans := min(x, y) * 2
if x != y {
ans++
}
return (ans + z) * 2
}
func min(a, b int) int { if b < a { return b }; return a }
cpp 解法, 执行用时: 12 ms, 内存消耗: 5.7 MB, 提交时间: 2023-06-25 09:30:00
class Solution {
public:
int longestString(int x, int y, int z) {
return (min(x, y) * 2 + (x != y) + z) * 2;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 39.4 MB, 提交时间: 2023-06-25 09:29:49
class Solution {
public int longestString(int x, int y, int z) {
return (Math.min(x, y) * 2 + (x != y ? 1 : 0) + z) * 2;
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-25 09:29:10
'''
如果没有AB，则AA和BB交替连接即可
如果有AB，它可以与自身连接，且只能插在 BB 和 AA 之间，即 BB + (ABABAB...) + AA
所以 AB 不会改变 AA 和 BB 交替连接的上限。
'''
class Solution:
def longestString(self, x: int, y: int, z: int) -> int:
return (min(x, y) * 2 + (x != y) + z) * 2