Construct the Longest New String

Construct the Longest New String

What is this problem about?

The Construct the Longest New String interview question is a combinatorial optimization problem. You are given three types of two-letter strings: "AA", "BB", and "AB". You have x of "AA", y of "BB", and z of "AB". You need to concatenate these strings to form the longest possible sequence such that the resulting string does not contain "AAA" or "BBB" as a substring.

Why is this asked in interviews?

Companies like Microsoft ask the Construct the Longest New String coding problem to test a candidate's ability to simplify a seemingly complex state-based problem. While it can be modeled with Dynamic Programming, the optimal solution is actually a mathematical "Brainteaser." It evaluates if you can identify the governing constraints (like the fact that "AA" must be followed by "BB", and vice-versa) to find a greedy or closed-form solution.

Algorithmic pattern used

This follows the Brainteaser, Math, Greedy interview pattern.

• "AB" can be placed anywhere as long as it doesn't violate rules, but actually, "AB" strings can just be chained together ("ABABAB...") indefinitely.
• "AA" and "BB" must alternate to avoid "AAA" or "BBB". For example: AABBAABB.