Construct the Longest New String - Solution & Explanation

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.