Can all AB strings always be used in the optimal solution?

Yes, because placing AB never creates AAA or BBB, they can always be used to separate AA and BB blocks.

What is the key dynamic programming pattern for this problem?

State transition DP tracking remaining counts of AA, BB, and AB while storing the last two characters prevents illegal substrings.

How do I handle consecutive AA or BB placements?

Only place AA if the last two characters are not both A, and BB if the last two characters are not both B, following DP transition rules.

What is the maximum string length for x = 3, y = 2, z = 2?

The maximum achievable length is 14, using an arrangement like "ABABAABBAABBAA".

What are common mistakes when solving 'Construct the Longest New String'?

Common mistakes include mismanaging DP indices, not using all AB strings greedily, and accidentally creating AAA or BBB substrings.

#2745

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

构造最长的新字符串

给你三个整数 x ， y 和 z 。这三个整数表示你有 x 个 "AA" 字符串， y 个 "BB" 字符串，和 z 个 "AB" 字符串。你需要选择这些字符串中的部分字符串（可以全部选择也可以一个都不选择），将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串 "AAA" 或者 "BBB…

数学动态规划贪心脑筋急转弯

题目描述

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

lightbulb

解题思路

方法一：分类讨论

我们观察发现，字符串 '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

8

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

speed

复杂度分析

指标	值
时间	complexity is O(x _y_ z) in the worst case due to three nested counts and possible transitions. Space complexity also depends on DP state storage and recursion stack, typically O(x _y_ z). Optimizations with memoization reduce repeated computations.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion of state representation and last-two-character tracking.
question_mark
Check understanding of how AB strings can always be safely inserted.
question_mark
Probe whether the candidate identifies DP transitions versus greedy simplifications.

warning

常见陷阱

外企场景

error
Forgetting to prevent AAA or BBB when placing AA or BB consecutively.
error
Overcomplicating AB handling instead of using all of them greedily.
error
Incorrect DP state indexing leading to repeated calculations or missed cases.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limit the number of AB strings that can be used and adjust DP transitions accordingly.
arrow_right_alt
Introduce a third forbidden substring pattern like AAB or BBA for stricter constraints.
arrow_right_alt
Allow any string length for AA, BB, and AB, requiring more general state tracking.

help

常见问题

外企场景

继续练习

#2310 个位数字为 K 的整数之和 #3260 找出最大的 N 位 K 回文数 #2750 将数组划分成若干好子数组的方式