Problem Description

You have three types of strings:

• x strings of "AA"
• y strings of "BB"
• z strings of "AB"

Your task is to select some (possibly all or none) of these strings and concatenate them in any order to create a new string. The constraint is that the resulting string must not contain "AAA" or "BBB" as a substring.

Return the maximum possible length of such a string.

For example, if you have strings "AA", "BB", and "AB", you could concatenate them as "AABBAB" (length 6), but you couldn't create "AAAA" since it contains "AAA" as a substring.

The key insight is understanding the placement rules:

• "AA" can only be followed by "BB" or "AB" (not another "AA" since that would create "AAA")
• "BB" can only be followed by "AA" or "AB" (not another "BB" since that would create "BBB")
• "AB" can be followed by any string type

The solution involves alternating between "AA" and "BB" strings to avoid creating forbidden substrings, then strategically placing the "AB" strings. The optimal arrangement depends on whether x < y, x > y, or x = y.

Intuition

The first observation is that we need to avoid creating "AAA" or "BBB". This means we can never place two "AA" strings consecutively or two "BB" strings consecutively.

Let's think about what can follow what:

• After "AA", we can only place "BB" or "AB" (not another "AA")
• After "BB", we can only place "AA" or "AB" (not another "BB")
• After "AB", we can place anything since it ends with 'B'

This suggests an alternating pattern between "AA" and "BB" would be optimal. The string "AB" is special - it acts as a "neutral" piece that can be inserted anywhere without creating forbidden patterns.

Now, how many "AA" and "BB" can we use in an alternating pattern?

• If we have equal amounts (x = y), we can use all of them by alternating: "AABBAABB..."
• If we have more "AA" than "BB" (x > y), we can start with "AA" and alternate: "AABBAABB...AA", using y + 1 of "AA" and all y of "BB"
• If we have more "BB" than "AA" (x < y), we can start with "BB" and alternate: "BBAABBAA...BB", using x + 1 of "BB" and all x of "AA"

The key insight is that "AB" strings are flexible - they can be placed at the beginning, end, or between any two strings without causing issues. Therefore, we should always use all z of them to maximize length.

Each string contributes 2 characters to the total length, so the formula becomes:

• When x < y: (x * 2 + z + 1) * 2 (using x AA's, x+1 BB's, and all z AB's)
• When x > y: (y * 2 + z + 1) * 2 (using y+1 AA's, y BB's, and all z AB's)
• When x = y: (x + y + z) * 2 (using all strings)

Learn more about Greedy, Math and Dynamic Programming patterns.

Solution Approach

The implementation is straightforward once we understand the pattern. We handle three distinct cases based on the relationship between x and y.

Case 1: When x < y

We can construct the string starting with "BB" and alternating: "BBAABBAA...BB".

• We use x strings of "AA" (all of them)
• We use x + 1 strings of "BB" (leaving y - x - 1 unused)
• We use all z strings of "AB"
• Total strings used: x + (x + 1) + z = 2x + z + 1
• Total length: (2x + z + 1) * 2

Case 2: When x > y

We can construct the string starting with "AA" and alternating: "AABBAABB...AA".

• We use y + 1 strings of "AA" (leaving x - y - 1 unused)
• We use y strings of "BB" (all of them)
• We use all z strings of "AB"
• Total strings used: (y + 1) + y + z = 2y + z + 1
• Total length: (2y + z + 1) * 2

Case 3: When x = y

We can use all "AA" and "BB" strings by alternating perfectly: "AABBAABB..." or "BBAABBAA...".

• We use all x strings of "AA"
• We use all y strings of "BB"
• We use all z strings of "AB"
• Total strings used: x + y + z
• Total length: (x + y + z) * 2

The "AB" strings can be placed flexibly - they can go at the beginning, end, or between any alternating pattern without creating forbidden substrings. This is why we always include all z of them in our final string.

The solution simply checks which case applies and returns the corresponding formula. Each string contributes exactly 2 characters, so we multiply the total number of strings by 2 to get the final length.

Example Walkthrough

Let's walk through an example where x = 3, y = 1, and z = 2.

This means we have:

• 3 strings of "AA"
• 1 string of "BB"
• 2 strings of "AB"

Since x > y (3 > 1), we fall into Case 2 of our solution approach.

Step 1: Determine how many of each string we can use

• We can use y + 1 = 1 + 1 = 2 strings of "AA"
• We can use all y = 1 string of "BB"
• We can use all z = 2 strings of "AB"

Step 2: Build an alternating pattern We start with "AA" and alternate with "BB":

• First "AA" → Current string: "AA"
• Then "BB" → Current string: "AABB"
• Then another "AA" → Current string: "AABBAA"

Step 3: Add the flexible "AB" strings The "AB" strings can be placed anywhere. For example:

• We could place them at the end: "AABBAAABAB"
• Or at the beginning: "ABABAABBAA"
• Or interspersed: "AAABBABAA"

All these arrangements are valid and have the same length.

Step 4: Calculate the total length

• Total strings used: 2 (AA) + 1 (BB) + 2 (AB) = 5 strings
• Each string contributes 2 characters
• Total length: 5 × 2 = 10 characters

Using our formula for Case 2:

• Length = (2y + z + 1) × 2
• Length = (2(1) + 2 + 1) × 2
• Length = 5 × 2 = 10

The maximum possible length is 10. Note that we had to leave 1 string of "AA" unused because using all 3 would create "AAA" somewhere in our string.

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the function performs a fixed number of operations regardless of the input values. It only involves:

• At most 2 comparison operations (x < y and x > y)
• A constant number of arithmetic operations (additions and multiplications)
• One return statement

All these operations take constant time and don't depend on the magnitude of the input values x, y, or z.

The space complexity is O(1) because the function uses only a constant amount of extra space. No additional data structures are created, and the space usage doesn't grow with the input size. The function only uses the input parameters and returns a single integer value.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Greedy Strategy

A common mistake is thinking we need complex dynamic programming or backtracking to find the optimal arrangement. Developers might try to enumerate all possible permutations of strings or use recursive approaches to test different combinations.

Why this happens: The problem seems like it requires exploring multiple arrangements to find the maximum length.

The reality: The problem has a greedy solution. Once we understand that we must alternate between "AA" and "BB" strings, and that "AB" strings can be placed anywhere, the optimal strategy becomes clear - use as many strings as possible while maintaining the alternating pattern.

2. Incorrect Calculation When x ≠ y

When implementing the formula for unequal x and y values, developers often make calculation errors:

Incorrect attempts:

# Wrong: Forgetting the +1 for the extra string
if x < y:
    return (x * 2 + z) * 2  # Missing the +1

# Wrong: Using min/max incorrectly
if x != y:
    return (min(x, y) * 2 + z) * 2  # Doesn't account for the extra string

Correct approach:

if x < y:
    return (x * 2 + z + 1) * 2  # x "AA"s + (x+1) "BB"s + z "AB"s
if x > y:
    return (y * 2 + z + 1) * 2  # (y+1) "AA"s + y "BB"s + z "AB"s

The key insight is that when counts are unequal, we can use one extra string of the more abundant type, creating patterns like "BB-AA-BB-AA-BB" (when y > x).

3. Overthinking "AB" String Placement

Developers might worry about where exactly to place the "AB" strings in the final arrangement, leading to unnecessary complexity in the code.

Why this happens: The problem statement emphasizes that the order matters and forbidden substrings must be avoided.

The solution: "AB" strings are special - they can be placed anywhere without creating "AAA" or "BBB". Whether you put them at the beginning, end, or interspersed throughout the alternating pattern, they won't violate the constraints. This is why we can simply add all z "AB" strings to our count.

4. Edge Case Handling

Some implementations try to handle edge cases like x=0, y=0, or z=0 separately, adding unnecessary complexity:

# Unnecessary complexity
if x == 0 and y == 0:
    return z * 2
elif x == 0:
    return (y + z) * 2
elif y == 0:
    return (x + z) * 2
# ... more cases

Better approach: The given formula naturally handles all edge cases:

• If x=0, y=0: The formula gives (0 + 0 + z) * 2 = z * 2 ✓
• If only x=0: The formula treats it as x < y case ✓
• If only y=0: The formula treats it as x > y case ✓

The mathematical formula is elegant enough to handle all cases without special conditions for zeros.