跳转至

2745. 构造最长的新字符串

题目描述

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

解法

方法一：分类讨论

我们观察发现，字符串 'AA' 之后只能跟 'BB'，而字符串 'AB' 可以放在字符串开头或结尾。因此：

  • 如果 $x \lt y$，那么我们可以先交替放置 'BBAABBAA..BB'，一共放置 $x$ 个 'AA' 和 $x+1$ 个 'BB'，然后放置剩余的 $z$ 个 'AB'，总长度为 $(x \times 2 + z + 1) \times 2$；
  • 如果 $x \gt y$，那么我们可以先交替放置 'AABBAABB..AA'，一共放置 $y$ 个 'BB' 和 $y+1$ 个 'AA'，然后放置剩余的 $z$ 个 'AB'，总长度为 $(y \times 2 + z + 1) \times 2$；
  • 如果 $x = y$，我们只需要交替放置 'AABB'，一共放置 $x$ 个 'AA' 和 $y$ 个 'BB'，然后放置剩余的 $z$ 个 'AB'，总长度为 $(x + y + z) \times 2$。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

1
2
3
4
5
6
7
class Solution:
    def longestString(self, x: int, y: int, z: int) -> int:
        if x < y:
            return (x * 2 + z + 1) * 2
        if x > y:
            return (y * 2 + z + 1) * 2
        return (x + y + z) * 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int longestString(int x, int y, int z) {
        if (x < y) {
            return (x * 2 + z + 1) * 2;
        }
        if (x > y) {
            return (y * 2 + z + 1) * 2;
        }
        return (x + y + z) * 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int longestString(int x, int y, int z) {
        if (x < y) {
            return (x * 2 + z + 1) * 2;
        }
        if (x > y) {
            return (y * 2 + z + 1) * 2;
        }
        return (x + y + z) * 2;
    }
};

1
2
3
4
5
6
7
8
9
func longestString(x int, y int, z int) int {
    if x < y {
        return (x*2 + z + 1) * 2
    }
    if x > y {
        return (y*2 + z + 1) * 2
    }
    return (x + y + z) * 2
}

1
2
3
4
5
6
7
8
9
function longestString(x: number, y: number, z: number): number {
    if (x < y) {
        return (x * 2 + z + 1) * 2;
    }
    if (x > y) {
        return (y * 2 + z + 1) * 2;
    }
    return (x + y + z) * 2;
}

评论