Question

2745. 构造最长的新字符串

English Version

题目描述

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

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