2745-构造最长的新字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你三个整数 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

下午两点【biIibiIi@灵茶山艾府】 直播讲题，不仅讲做法，还会教你如何一步步思考，记得关注哦~

如果没有 AB，那么 AA 和 BB 只能交替连接，答案为

(\min(x,y)\cdot 2 + [x\ne y])\cdot 2

如果有 AB，它可以与自身连接，且只能插在 BB 和 AA 之间，即 BB + (ABABAB…) + AA。

或者接在后缀 BB 之后，或者加到前缀 AA 之前。

所以 AB 不会改变 AA 和 BB 交替连接的上限。

所以答案为

(\min(x,y)\cdot 2 + [x\ne y] + z)\cdot 2

[sol-Python3]
1
2
3
class Solution:
    def longestString(self, x: int, y: int, z: int) -> int:
        return (min(x, y) * 2 + (x != y) + z) * 2
[sol-Java]
1
2
3
4
5
class Solution {
    public int longestString(int x, int y, int z) {
        return (Math.min(x, y) * 2 + (x != y ? 1 : 0) + z) * 2;
    }
}
[sol-C++]
1
2
3
4
5
6
class Solution {
public:
    int longestString(int x, int y, int z) {
        return (min(x, y) * 2 + (x != y) + z) * 2;
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
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 }

复杂度分析

  • 时间复杂度：\mathcal{O}(1)。
  • 空间复杂度：\mathcal{O}(1)。

附：记忆化搜索

定义 dfs}(x,y,z,k)，其中 x,y,z 为 AA/BB/AB 的剩余数量，k=0,1,2 表示上一个字符串是 AA/BB/AB，此时可以构造出的字符串的最大可能长度。

类似 状态机 DP ，分类讨论：

  • AA 后面只能接 BB；
  • BB 后面可以接 AA 或 AB；
  • AB 后面可以接 AA 或 AB。
[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
@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))
[sol-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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}
			}
		}
	}
	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 }
 Comments
On this page
2745-构造最长的新字符串
  1. 附：记忆化搜索