#2745

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Construct the Longest New String

Maximize the length of a string built from AA, BB, and AB without creating triple repeats using DP and greedy logic.

math dynamic programming greedy brainteaser

Problem Statement

You are given three integers x, y, and z representing counts of strings: x copies of "AA", y copies of "BB", and z copies of "AB". Your goal is to concatenate some or all of these strings to form a new string while ensuring it does not contain "AAA" or "BBB" as a substring.

Return the maximum possible length of such a string. For example, with x = 2, y = 5, z = 1, the string "BBAABBAABBAB" has length 12 and satisfies the constraints, demonstrating the need for careful ordering to avoid invalid repeats.

Examples

Example 1

Input: x = 2, y = 5, z = 1

Output: 12

We can concatenate the strings "BB", "AA", "BB", "AA", "BB", and "AB" in that order. Then, our new string is "BBAABBAABBAB". That string has length 12, and we can show that it is impossible to construct a string of longer length.

Example 2

Input: x = 3, y = 2, z = 2

Output: 14

We can concatenate the strings "AB", "AB", "AA", "BB", "AA", "BB", and "AA" in that order. Then, our new string is "ABABAABBAABBAA". That string has length 14, and we can show that it is impossible to construct a string of longer length.

Constraints

1 <= x, y, z <= 50

Solution Approach

Dynamic Programming State Representation

Model the problem with a 3D DP array dp[x_remaining][y_remaining][z_remaining], tracking the last two characters used. Each state records the maximum string length achievable from that point, reflecting the state transition pattern critical for correctness.

Greedy Placement of AB Strings

All AB strings can be used without risk of creating AAA or BBB. Insert them strategically to separate AA and BB blocks, simplifying DP states. This greedy step reduces the number of transitions needed to find the optimal solution.

Transition Rules and Recursion

From any DP state, attempt to place AA if last two chars are not AA, BB if last two chars are not BB, or AB freely. Recurse to the next state and record the maximum achievable length. This approach balances DP correctness with greedy efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Case Discussion

We observe that the string 'AA' can only be followed by 'BB', and the string 'AB' can be placed at the beginning or end of the string. Therefore:

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

Continue Practicing

#2310 sum of numbers with units digit k #3260 find the largest palindrome divisible by k #2750 ways to split array into good subarrays