How to Solve Construct the Longest New String

This problem requires constructing the longest string from given AA, BB, and AB pieces without producing AAA or BBB. Use state transition dynamic programming to track remaining counts and the last two characters efficiently. Greedy choices for AB placement simplify the state, ensuring an optimal maximum length solution in all cases.

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

Time complexity is O(xyz) 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(xyz). 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.

How GhostInterview Helps

• Automatically evaluates DP states and tracks last-two-character transitions efficiently.
• Highlights greedy AB placements and flags illegal AAA or BBB sequences in intermediate strings.
• Provides detailed step-by-step reasoning for maximum string length decisions, avoiding common pitfalls.

Topic Pages

• Math
• Dynamic Programming
• Greedy
• Brainteaser

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.