2745. Construct the Longest New String Solution

The problem

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

Python

def maxLengthString(x, y, z):
    return 2 * (x + y + z) + (1 if x != y else 0)

x, y, z = 2, 5, 1
print(maxLengthString(x, y, z))

Java

public class Solution {
    public int maxLengthString(int x, int y, int z) {
        return 2 * (x + y + z) + (x != y ? 1 : 0);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxLengthString(2, 5, 1));
    }
}

C++

#include <iostream>

int maxLengthString(int x, int y, int z) {
    return 2 * (x + y + z) + (x != y);
}

int main() {
    int x = 2, y = 5, z = 1;
    std::cout << maxLengthString(x, y, z) << std::endl;
    return 0;
}

JavaScript

function maxLengthString(x, y, z) {
    return 2 * (x + y + z) + (x !== y ? 1 : 0);
}

console.log(maxLengthString(2, 5, 1));

#include <stdio.h>

int maxLengthString(int x, int y, int z) {
    int minVal = x < y ? x : y;
    return 2 * (x + y + z) + (x != y);
}

int main() {
    int x = 2, y = 5, z = 1;
    printf("%d\n", maxLengthString(x, y, z));
    return 0;
}

using System;

class Program {
    static int MaxLengthString(int x, int y, int z) {
        return 2 * (x + y + z) + (x != y ? 1 : 0);
    }

    static void Main() {
        int x = 2, y = 5, z = 1;
        Console.WriteLine(MaxLengthString(x, y, z));
    }
}

This Python solution directly calculates the maximum possible length by considering maximum usage of 'AB' in separation and adding extra if x differs from y.

Complexity

Time Complexity: O(1) since computations are done directly.
Space Complexity: O(1) because no additional data structures are utilized.

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.

Python

def maxLengthString(x, y, z):
    maxLength = x + y + z
    minimizeRepeat = min(x, y)
    return minimizeRepeat * 4 + 2 * (maxLength - minimizeRepeat)

print(maxLengthString(3, 2, 2))

Java

public class Solution {
    public int maxLengthString(int x, int y, int z) {
        int max_strings = x + y + z;
        int min_strings = Math.min(x, y);
        return min_strings * 4 + 2 * (max_strings - min_strings);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxLengthString(3, 2, 2));
    }
}

C++

#include <iostream>

int maxLengthString(int x, int y, int z) {
    int maxLength = 2 * (x + y + z) + 1, minimizeRepeat = (x < y) ? x : y;
    return 4 * minimizeRepeat + 2 * (x + y + z - minimizeRepeat);
}

int main() {
    std::cout << maxLengthString(3, 2, 2) << std::endl;
    return 0;
}

JavaScript

function maxLengthString(x, y, z) {
    let maxLength = x + y + z;
    let minimizeRepeat = Math.min(x, y);
    return minimizeRepeat * 4 + 2 * (maxLength - minimizeRepeat);
}

console.log(maxLengthString(3, 2, 2));

#include <stdio.h>

int maxLengthString(int x, int y, int z) {
    int max_strings = x + y + z;
    int min_strings = x < y ? x : y;
    return min_strings * 4 + 2 * (max_strings - min_strings);
}

int main() {
    int x = 3, y = 2, z = 2;
    printf("%d\n", maxLengthString(x, y, z));
    return 0;
}

using System;

class Program {
    static int MaxLengthString(int x, int y, int z) {
        int maxLength = x + y + z;
        int minimizeRepeat = Math.Min(x, y);
        return minimizeRepeat * 4 + 2 * (maxLength - minimizeRepeat);
    }

    static void Main() {
        Console.WriteLine(MaxLengthString(3, 2, 2));
    }
}

A Python solution attending path variant constructs by distributing available strings effectively, aiming to optimize by conservation of strategic bridges using 'AB'.

Complexity

Time Complexity: O(1) since calculations remain constant.
Space Complexity: O(1) as the program maintains a limited footprint.

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

TypeScript

function longestString(x: number, y: number, z: number): number {
    if (x < y) {
        return (x * 2 + z + 1) * 2;
    }
    if (x > y) {
        return (y * 2 + z + 1) * 2;
    }
    return (x + y + z) * 2;
}

func longestString(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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach Using Balancing	Time Complexity: O(1) since computations are done directly. Space Complexity: O(1) because no additional data structures are utilized.
Dynamic Tenet with Separation Strategy	Time Complexity: O(1) since calculations remain constant. Space Complexity: O(1) as the program maintains a limited footprint.
Case Discussion	–

Complexity analysis

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

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.

Construct the Longest New String solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Balancing

Approach 2: Dynamic Tenet with Separation Strategy

Approach 3: Case Discussion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Construct the Longest New String solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Balancing

Approach 2: Dynamic Tenet with Separation Strategy

Approach 3: Case Discussion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems