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.

Description Hints 3 Solution Video 9:08

2745. Construct the Longest New String

Medium53.8% acceptance2 companies

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

Asked at 2 companies

Guidewire Microsoft

Topics

Hints open one at a time

Hint 1

It can be proved that ALL “AB”s can be used in the optimal solution. (1) If the final string starts with 'A', we can put all unused “AB”s at the very beginning. (2) If the final string starts with 'B' (meaning) it starts with “BB”, we can put all unused “AB”s after the 2nd 'B'.

Hint 2

Using “AB” doesn’t increase the number of “AA”s or “BB”s we can use. If we put an “AB” after “BB”, then we still need to append “AA” as before, so it doesn’t change the state.

Hint 3

We only need to consider strings “AA” and “BB”; we can either use the pattern “AABBAABB…” or the pattern “BBAABBAA…”, depending on which one of x and y is larger.

9:08

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestString(self, x: int, y: int, z: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

2
5
1

Input

3
2
2

Your code is saved on this device.Solution