Get started

Construct the Longest New String — Medium Problem & Solution

You have x copies of the string "AA", y copies of "BB" and z copies of "AB".

  • Difficulty: Medium
  • Topics: Math, Greedy, Brainteaser
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have x copies of the string "AA", y copies of "BB" and z copies of "AB". Pick any number of them (possibly none, possibly all) and glue them together in any order.

The result must not contain "AAA" or "BBB" as a substring. Return the maximum possible length of the result.

Example 1

Input: x = 2, y = 5, z = 1
Output: 12
Explanation: `"BB" "AA" "BB" "AA" "BB" "AB"` gives `BBAABBAABBAB`, length 12.

Example 2

Input: x = 3, y = 2, z = 2
Output: 14
Explanation: `"AB" "AB" "AA" "BB" "AA" "BB" "AA"` gives `ABABAABBAABBAA`.

Example 3

Input: x = 1, y = 1, z = 1
Output: 6

Constraints

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

How to solve Construct the Longest New String

"AA" and "BB" must strictly alternate, while every "AB" can be used: a block ABAB…AB fits in front of an "AA" (or alone). So the answer is a formula.

Approach

  1. Use all z copies of "AB" as one block ABAB…AB.
  2. Alternate "AA" and "BB": with x == y use all of both; otherwise use min(x, y) of each plus one more of the larger kind (the alternation can start and end with it).
  3. The answer is 2 · (2 · min(x, y) + (x != y ? 1 : 0) + z).

Why it works

After "AA" only "BB" may follow, and two "BB"s can never touch, so the "AA" and "BB" pieces alternate and their counts differ by at most one. Every "AB" can always be used: when x >= y, put the chain AB…AB first and then AA BB AA … (ABAA is fine); when y > x, write BB AA … BB and append the chain (BBAB is fine). So the bound is reached.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • "AB" followed by "BB" makes ABBB — so the AB block must not sit right before a "BB".
  • When x == y there is no extra piece: the +1 applies only to unequal counts.
  • The answer is a length in characters, so multiply the number of pieces by 2.

Reference solution

Python

def longestString(x: int, y: int, z: int) -> int:
    pairs = 2 * min(x, y) + (1 if x != y else 0)
    return 2 * (pairs + z)

JavaScript

var longestString = function(x, y, z) {
    var pairs = 2 * Math.min(x, y) + (x !== y ? 1 : 0);
    return 2 * (pairs + z);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 307 math problems · the whole catalogue

Learn the technique: Greedy Algorithms