LeetCode 2745 - Construct the Longest New String

The problem gives us three types of fixed two-character strings: - "AA" appears x times - "BB" appears y times - "AB" appears z times We may choose any subset of these strings and concatenate them in any order.

leetcodemediummathdynamic-programminggreedybrainteaser

LeetCode Problem 2745

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Greedy, Brainteaser

Solution

LeetCode 2745 - Construct the Longest New String

Problem Understanding

The problem gives us three types of fixed two-character strings:

  • "AA" appears x times
  • "BB" appears y times
  • "AB" appears z times

We may choose any subset of these strings and concatenate them in any order. The goal is to build the longest possible resulting string while ensuring that the final string never contains:

  • "AAA"
  • "BBB"

as substrings.

Since each building block has length 2, every selected string contributes exactly 2 characters to the answer. Therefore, the problem effectively becomes:

How many blocks can we use while keeping the concatenated result valid?

The dangerous situations occur when we place two incompatible blocks next to each other. For example:

  • "AA" followed by "AA" creates "AAAA", which contains "AAA"
  • "BB" followed by "BB" creates "BBBB", which contains "BBB"

So consecutive "AA" blocks are forbidden, and consecutive "BB" blocks are forbidden.

However:

  • "AA" can safely connect to "BB"
  • "BB" can safely connect to "AA"
  • "AB" is flexible and never directly creates triples on its own

The constraints are very small:

  • 1 <= x, y, z <= 50

This means even exponential or dynamic programming solutions would technically fit, but the structure of the problem allows a much simpler mathematical observation.

Several edge cases are important:

  • One of x or y may be much larger than the other
  • All "AB" strings are always usable
  • We may not be able to use every "AA" or "BB" block because identical blocks cannot appear consecutively
  • The optimal arrangement depends on alternating "AA" and "BB" as much as possible

Understanding that the restriction only depends on neighboring block transitions is the key simplification.

Approaches

Brute Force Approach

A brute force solution would try every possible ordering of the available strings.

We could recursively build every valid concatenation by choosing one remaining block at a time. At each step, we would append a block only if doing so does not create "AAA" or "BBB".

This approach is correct because it explores every legal construction and records the maximum length encountered.

However, it is extremely inefficient. If we have up to x + y + z = 150 blocks, the number of possible permutations becomes astronomically large. Even with pruning, the search space grows exponentially.

Therefore, brute force is not practical.

Key Insight

The important observation is that:

  • "AA" blocks cannot touch other "AA" blocks
  • "BB" blocks cannot touch other "BB" blocks

This means the only way to use many "AA" blocks is to separate them using "BB" blocks, and vice versa.

Effectively, "AA" and "BB" must alternate.

Suppose:

  • x <= y

Then we can arrange:

BB AA BB AA BB ...

Every "AA" needs a "BB" separator around it.

This means:

  • We can use all smaller-type blocks
  • We can use at most one more block of the larger type

So the maximum usable count of "AA" and "BB" together is:

2 * min(x, y) + (1 if x != y else 0)

This simplifies to:

2 * min(x, y) + (x != y)

Every "AB" block is always usable because it never creates forbidden triples when appended carefully. Therefore, we always use all z of them.

Since each block contributes length 2, the final answer becomes:

(2 * min(x, y) + (x != y) + z) * 2

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((x+y+z)!) O(x+y+z) Tries all valid permutations recursively
Optimal O(1) O(1) Uses mathematical observation about alternation

Algorithm Walkthrough

  1. Compute the smaller value between x and y.

This represents how many complete alternations between "AA" and "BB" we can form. 2. Use all pairs of alternating blocks.

If min(x, y) = k, then we can safely use:

AA BB AA BB ...

for a total of 2 * k blocks. 3. Check whether one type has extra blocks remaining.

If x != y, then the larger side can contribute exactly one additional block at the beginning or end of the sequence.

For example:

BB AA BB AA BB

The final "BB" is valid because it is not adjacent to another "BB". 4. Add all "AB" blocks.

Every "AB" block can be inserted safely and always contributes positively to the total length. 5. Multiply the total number of usable blocks by 2.

Every block has exactly two characters.

Why it works

The core invariant is that identical double-letter blocks cannot be adjacent.

Therefore:

  • "AA" blocks require "BB" separators
  • "BB" blocks require "AA" separators

The maximum alternating sequence between two categories always uses all blocks of the smaller category and at most one extra block from the larger category.

Since "AB" blocks do not introduce forbidden triples in optimal placements, all of them can always be included.

This guarantees the formula produces the maximum possible valid length.

Python Solution

class Solution:
    def longestString(self, x: int, y: int, z: int) -> int:
        usable_pairs = 2 * min(x, y)

        if x != y:
            usable_pairs += 1

        total_blocks = usable_pairs + z

        return total_blocks * 2

The implementation directly follows the mathematical derivation.

First, we compute how many alternating "AA" and "BB" blocks can be used. The value 2 * min(x, y) represents all perfectly alternating pairs.

Next, if one side has additional blocks remaining, we can safely append exactly one more block of that type. This is handled by checking x != y.

After that, we add all "AB" blocks because they are always usable.

Finally, since every block has length 2, we multiply the total block count by 2 and return the result.

The implementation uses only constant space and constant time.

Go Solution

func longestString(x int, y int, z int) int {
    smaller := x
    if y < x {
        smaller = y
    }

    usablePairs := 2 * smaller

    if x != y {
        usablePairs++
    }

    totalBlocks := usablePairs + z

    return totalBlocks * 2
}

The Go implementation mirrors the Python logic exactly.

Since Go does not provide a built-in min function for integers, we compute the smaller value manually using a simple conditional check.

No special overflow handling is needed because the maximum possible answer is very small:

(2 * 50 + 1 + 50) * 2 = 302

which easily fits inside a standard Go int.

Worked Examples

Example 1

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

We compute:

Variable Value
min(x, y) 2
alternating blocks 2 * 2 = 4
extra larger block 1
usable AA/BB blocks 5
AB blocks 1
total blocks 6
final length 12

A valid arrangement is:

BB AA BB AA BB AB

Resulting string:

BBAABBAABBAB

Length:

12

Example 2

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

We compute:

Variable Value
min(x, y) 2
alternating blocks 4
extra larger block 1
usable AA/BB blocks 5
AB blocks 2
total blocks 7
final length 14

One valid arrangement:

AB AB AA BB AA BB AA

Resulting string:

ABABAABBAABBAA

Length:

14

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only a few arithmetic operations are performed
Space O(1) No additional data structures are used

The solution is purely mathematical. Regardless of the input values, the algorithm performs the same constant number of operations.

No loops, recursion, or auxiliary storage are required.

Test Cases

sol = Solution()

assert sol.longestString(2, 5, 1) == 12  # provided example 1
assert sol.longestString(3, 2, 2) == 14  # provided example 2

assert sol.longestString(1, 1, 1) == 6   # perfectly balanced counts
assert sol.longestString(1, 2, 3) == 12  # extra BB block usable
assert sol.longestString(2, 1, 3) == 12  # extra AA block usable

assert sol.longestString(5, 5, 5) == 30  # all blocks usable
assert sol.longestString(50, 50, 50) == 300  # maximum balanced input

assert sol.longestString(50, 1, 1) == 8  # many AA blocks cannot be used
assert sol.longestString(1, 50, 1) == 8  # many BB blocks cannot be used

assert sol.longestString(10, 9, 0) == 38  # no AB blocks
assert sol.longestString(9, 10, 0) == 38  # symmetric case

assert sol.longestString(1, 1, 50) == 104  # AB blocks dominate

Test Summary

Test Why
(2,5,1) Validates provided example
(3,2,2) Validates provided example
(1,1,1) Small balanced input
(1,2,3) Tests one extra BB block
(2,1,3) Tests one extra AA block
(5,5,5) All blocks usable
(50,50,50) Maximum balanced constraint
(50,1,1) Large imbalance toward AA
(1,50,1) Large imbalance toward BB
(10,9,0) No AB blocks
(9,10,0) Symmetry validation
(1,1,50) Heavy use of AB blocks

Edge Cases

One important edge case occurs when one of x or y is much larger than the other. For example, if x = 50 and y = 1, a naive implementation might incorrectly assume that most "AA" blocks can still be used. In reality, consecutive "AA" blocks create forbidden "AAA" substrings, so only one extra "AA" beyond the alternating sequence is usable. The formula correctly limits usage to 2 * min(x, y) + 1.

Another important case is when x and y are equal. In this situation, there is no larger side that can contribute an extra block. A buggy implementation might accidentally add one more block anyway. The condition if x != y prevents this mistake and ensures only perfectly alternating sequences are counted.

A third edge case occurs when z is very large. Since "AB" blocks are always safe to include, the optimal strategy always uses every "AB" block. Some incorrect greedy implementations may unnecessarily exclude them due to local adjacency concerns. This solution avoids that issue entirely because the mathematical observation guarantees all "AB" blocks can contribute to the answer.