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)\)。

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

2745. 构造最长的新字符串

题目描述

解法

方法一：分类讨论

评论