Skip to main content
Talentd

Construct the Longest New String - Solution & Explanation

MediumMathDynamic ProgrammingGreedyBrainteaser17 min readAsked at: Microsoft, Guidewire
Practice this problem

Problem Statement

You are given three integers x, y, and z.

You have x strings equal to "AA", y strings equal to "BB", and z strings equal to "AB". You want to choose some (possibly all or none) of these strings and concatenate them in some order to form a new string. This new string must not contain "AAA" or "BBB" as a substring.

Return the maximum possible length of the new string.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

Input: x = 2, y = 5, z = 1
Output: 12
Explanation: We can concactenate 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
Explanation: We can concactenate 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

Approach Overview

Problem Overview: You are given counts of three string pieces: "AA", "BB", and "AB". The task is to construct the longest possible string by concatenating these pieces without ever creating the substrings "AAA" or "BBB". Each piece has length 2, so the challenge is deciding the order that avoids three identical consecutive characters.

Approach 1: Greedy Approach Using Balancing (O(1) time, O(1) space)

The key observation is that two "AA" pieces cannot be placed back‑to‑back because "AA" + "AA" creates "AAAA", which contains "AAA". The same restriction applies to "BB". This means "AA" and "BB" must alternate whenever both exist. A greedy strategy pairs them as much as possible using min(x, y). If one type has an extra piece, you can safely add exactly one more at either end, but not two consecutively. The "AB" pieces naturally break runs because they end with B, so they can be appended after "BB" or other "AB" pieces without forming forbidden triples. Counting the maximum valid placements directly yields the final length in constant time. This approach works because the only dangerous patterns are consecutive identical blocks, so balancing the counts eliminates invalid configurations. Greedy reasoning like this frequently appears in greedy and math problems where local constraints determine the global maximum.

Approach 2: Dynamic Tenet with Separation Strategy (O(n) states, O(n) space)

A dynamic programming formulation helps if you want to explicitly model valid transitions. Track the remaining counts of AA, BB, and AB, along with the type of the last block used. The state transition checks whether adding another block would create AAA or BBB. For example, adding AA is disallowed if the previous block already ended with AA, while AB can follow most blocks because it introduces a separating character. The DP explores valid placements and records the maximum achievable length. Each transition reduces one block count, ensuring the state space stays manageable. This method makes the constraints explicit and is useful if the rules become more complex, which is common in dynamic programming interview variants.

Recommended for interviews: The greedy balancing approach is the expected solution. It runs in constant time and relies on a simple observation about alternating AA and BB blocks. Explaining the constraint that identical blocks cannot appear consecutively demonstrates problem understanding, while deriving the direct count formula shows strong optimization skills.

Approach 1: Greedy Approach Using Balancing

To avoid having 'AAA' or 'BBB', we can construct a string using a greedy approach by alternately using 'AA' and 'BB'. We can intersperse 'AB' between sequences of 'AA' or 'BB' where needed. The goal is to balance the number of 'AA' and 'BB' used and maximize the use of 'AB' to separate them if necessary.

The idea is to:

  • Use 'AA' and 'BB' to construct a string, alternating between them. This acts as a base construction.
  • Use 'AB' to separate blocks of 'AA' and 'BB' to prevent occurrences of 'AAA' or 'BBB'.

This C solution calculates the overall length of the new string by summing up both 'AA' and 'BB' string lengths and adding twice the 'AB' strings, considering also if x and y are not equal we can additionally use one more 'AA' or 'BB' because the alternation will accommodate one extra at the ends.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) since it computes the result directly.
Space Complexity: O(1) since it uses a constant amount of space.

Try this approach in the editor →

Approach 2: Dynamic Tenet with Separation Strategy

This approach leverages the idea of dynamic choices between construction paths for each set input. By understanding each 'AA', 'BB', and 'AB' unit in constructing long sequences, including alternating and staggered constructs with 'AB' as separators, it aims at optimal spacing and filling.

The strategy stands as:

  • Choose a base base which cycles through 'AA' and 'BB', fixed capacity interwoven via all available 'AB'.
  • Utilize 'AB' as necessary to terminate sequences avoiding triple repetition illegality.

This approach diversifies between pairing and increment patterns by qualifying separation points as essential blocks, optimizing the total result by multiplicative capacities.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) because direct calculations are employed.
Space Complexity: O(1) since no extra space allocations are needed.

Try this approach in the editor →

Approach 3: 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:

  • If x < y, we can first alternately place 'BBAABBAA..BB', placing a total of x 'AA' and x+1 'BB', then place the remaining z 'AB', with a total length of (x times 2 + z + 1) times 2;
  • If x > y, we can first alternately place 'AABBAABB..AA', placing a total of y 'BB' and y+1 'AA', then place the remaining z 'AB', with a total length of (y times 2 + z + 1) times 2;
  • If x = y, we only need to alternately place 'AABB', placing a total of x 'AA' and y 'BB', then place the remaining z 'AB', with a total length of (x + y + z) times 2.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach Using Balancing

Time Complexity: O(1) since it computes the result directly.
Space Complexity: O(1) since it uses a constant amount of space.

Dynamic Tenet with Separation Strategy

Time Complexity: O(1) because direct calculations are employed.
Space Complexity: O(1) since no extra space allocations are needed.

Case Discussion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy BalancingO(1)O(1)Best for interviews and production solutions when counts of blocks are known and constraints allow direct reasoning.
Dynamic Tenet with Separation StrategyO(x + y + z)O(x + y + z)Useful when demonstrating correctness through explicit state transitions or when constraints are extended.

Video Solution

Leetcode BiWeekly contest 107 - Medium - Construct the Longest New String • Prakhar Agrawal • 792 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Construct the Longest New String easy or hard?
LeetCode classifies this problem as Medium. The challenge lies in recognizing the greedy constraint about consecutive AA and BB blocks. Once that insight is clear, the final formula and implementation become straightforward.
Construct the Longest New String Python/Java solution
Most implementations compute the maximum number of alternating AA and BB blocks and add AB blocks afterward. The logic is only a few lines in Python, Java, C++, or JavaScript because the result depends on simple count comparisons rather than iteration.
How to solve Construct the Longest New String in O(1)?
Observe that AA and BB blocks cannot appear consecutively. Pair them using min(x, y) to form an alternating sequence, optionally add one extra block from the larger group, and include all AB blocks since they help break character runs. The total length is calculated directly from these counts.
What is the best approach for Construct the Longest New String?
The greedy balancing approach is the optimal solution. It alternates AA and BB blocks as much as possible and uses AB blocks to extend the sequence without forming AAA or BBB. This method computes the final length directly in O(1) time and O(1) space.
Is Construct the Longest New String asked at Google/Amazon/Meta?
Problems involving greedy sequencing and avoiding invalid patterns appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this question test your ability to reason about constraints and construct maximum-length strings safely.
What data structure is used in Construct the Longest New String?
The optimal solution does not require complex data structures. It relies on greedy counting and arithmetic. A dynamic programming variant may track states using arrays or memoization to represent remaining blocks and the last block used.
What is the time complexity of Construct the Longest New String?
The optimal greedy solution runs in O(1) time because the result is derived using simple arithmetic on the counts of AA, BB, and AB blocks. Space complexity is also O(1) since no additional data structures are required.

Ready to solve this problem?

Practice Construct the Longest New String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer