Construct the Longest New String

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.

Examples

Example 1

1
2
3
4


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

1
2
3
4


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

Solution

Method 1 – Greedy Alternating Construction

Intuition

To maximize the length of the new string without having “AAA” or “BBB” as a substring, we should alternate between “AA” and “BB” as much as possible, using “AB” as a safe separator. The greedy approach is to always add the pair that doesn’t create three consecutive same letters, and use “AB” to break up runs if possible.

Approach

The maximum number of “AA” and “BB” pairs that can be used without creating three consecutive same letters is min(x, y) + min(x, y) + (z > 0 ? 1 : 0).
Use as many “AB” as possible to separate runs of “AA” and “BB”.
The optimal answer is 2 * (min(x, y) + min(x, y) + z) if z > 0, but we need to be careful not to overcount.
The actual formula is: 2 * (min(x, y) * 2 + (z if z > 0 else 0)) but capped by the available x, y, z.
The best greedy is: if x == y, use all x, y, and as many z as possible (at most one extra). If x != y, use all of the smaller, all of the larger minus one, and as many z as possible.
The final answer is 2 * (min(x, y) * 2 + min(abs(x - y), 1) + z).

Code

1
2
3
4
5
6
7


class Solution {
public:
    int longestString(int x, int y, int z) {
        int pairs = min(x, y);
        return 2 * (pairs * 2 + (x != y) + z);
    }
};

1
2
3
4
5
6
7


func LongestString(x, y, z int) int {
    pairs := x
    if y < x { pairs = y }
    extra := 0
    if x != y { extra = 1 }
    return 2 * (pairs*2 + extra + z)
}

1
2
3
4
5
6


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

1
2
3
4
5
6


class Solution {
    fun longestString(x: Int, y: Int, z: Int): Int {
        val pairs = minOf(x, y)
        return 2 * (pairs * 2 + if (x != y) 1 else 0 + z)
    }
}

1
2
3
4


class Solution:
    def longestString(self, x: int, y: int, z: int) -> int:
        pairs = min(x, y)
        return 2 * (pairs * 2 + (x != y) + z)

1
2
3
4
5
6


impl Solution {
    pub fn longest_string(x: i32, y: i32, z: i32) -> i32 {
        let pairs = x.min(y);
        2 * (pairs * 2 + if x != y { 1 } else { 0 } + z)
    }
}

1
2
3
4
5
6


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

Complexity

⏰ Time complexity: O(1), as the answer is computed with a few arithmetic operations.
🧺 Space complexity: O(1), only a few variables are used.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Greedy Alternating Construction#

Intuition#

Approach#

Code#

Complexity#