# Construct the Longest New String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-the-longest-new-string)
Canonical: https://scaleengineer.com/dsa/problems/construct-the-longest-new-string
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Zalando](https://scaleengineer.com/companies/zalando), [Guidewire](https://scaleengineer.com/companies/guidewire)
---
## 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.

**Example 1:**

**Input:** x = 2, y = 5, z = 1
**Output:** 12
**Explanation:** We can concatenate 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:**

**Input:** x = 3, y = 2, z = 2
**Output:** 14
**Explanation:** We can concatenate 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`

# Approaches
## Brute-Force Recursion
This approach attempts to solve the problem by exploring every possible valid sequence of string concatenations. It uses a recursive function to build the string step-by-step, at each point deciding which type of string block to add next based on the last block added to avoid forming "AAA" or "BBB".
**Time:** O(2^(x+y+z)) - In the worst case, the function can branch into two recursive calls at each step. With a maximum recursion depth of `x+y+z`, the number of operations grows exponentially, making it infeasible for the given constraints. · **Space:** O(x + y + z) - This is for the maximum depth of the recursion stack.
**Pros:** Conceptually simple and directly models the problem statement.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
A recursive function, say `solve(x, y, z, lastBlockType)`, is defined to calculate the maximum length. The state of the recursion is determined by the remaining number of "AA", "BB", and "AB" strings (`x`, `y`, `z`) and the type of the last block added (`lastBlockType`). This last parameter is crucial to enforce the constraint that no three consecutive identical characters appear. For instance, if the last block added was "AA", the next block must start with a 'B', which means only "BB" can be appended. If the last block was "BB" or "AB", the string ends with a 'B', so the next block must start with an 'A', allowing either "AA" or "AB". The function explores these possibilities, and the final answer is the maximum length found among all valid sequences. Without memoization, this leads to an exponential number of calls as the same subproblems are solved repeatedly.
### Algorithm
*   Define a recursive function `solve(x, y, z, lastBlock)` that returns the maximum additional length possible given the remaining counts of strings and the type of the last block added.
*   `lastBlock` can be an enumeration or integer representing "AA", "BB", or "AB".
*   The base case is when no more valid strings can be added, returning 0.
*   The recursive step explores all valid next moves based on `lastBlock`:
    *   If the last block was "AA", the next must be "BB". We make a recursive call `solve(x, y - 1, z, "BB")`.
    *   If the last block was "BB" or "AB" (which ends in 'B'), the next can be "AA" or "AB". We make two recursive calls, `solve(x - 1, y, z, "AA")` and `solve(x, y, z - 1, "AB")`, and take the maximum result.
*   The main function initiates three separate recursive chains, one for each possible starting block ("AA", "BB", "AB"), and returns the maximum length found.

## Dynamic Programming with Memoization
This approach optimizes the brute-force recursion by using dynamic programming with memoization. It recognizes that the recursive solution involves many overlapping subproblems—the same state `(x, y, z, lastBlockType)` is reached through different paths. By storing the result for each state after computing it once, we can avoid redundant calculations and reduce the time complexity from exponential to polynomial.
**Time:** O(x * y * z) - There are `x * y * z * 3` possible states. Each state is computed once, and the computation for each state takes constant time. · **Space:** O(x * y * z) - The dominant factor is the size of the memoization table. The recursion stack depth adds a smaller `O(x+y+z)` term.
**Pros:** Guaranteed to find the optimal solution.; Efficient enough for the given constraints.
**Cons:** Requires significant memory for the memoization table.; More complex to implement than the greedy approach.
### Explanation
We define a state by `(x, y, z, lastBlockType)`, representing the remaining counts of each string type and the last block added. A multi-dimensional array, `memo`, is used to cache the results. When the recursive function `solve(x, y, z, lastBlockType)` is called, it first checks the `memo` table. If a result for the current state exists, it's returned instantly. Otherwise, the function computes the result by exploring valid next moves, just like the brute-force method. The key difference is that the newly computed result is stored in the `memo` table before being returned. This ensures that each of the `O(x*y*z)` unique states is computed only once, making the solution efficient enough to pass within the given time limits.
### Algorithm
*   Use the same recursive structure as the brute-force approach: `solve(x, y, z, lastBlockType)`.
*   Introduce a memoization table, e.g., a 4D array `memo[x+1][y+1][z+1][3]`, to store the results of previously computed subproblems. The last dimension corresponds to the `lastBlockType`.
*   Initialize the memoization table with a sentinel value (like -1) to indicate that a state has not been computed.
*   In the recursive function, before any computation, check if `memo[x][y][z][lastBlockType]` already contains a valid result. If so, return it immediately.
*   If the result is not in the table, compute it using the same recursive logic as the brute-force method.
*   Before returning the computed result, store it in `memo[x][y][z][lastBlockType]` for future use.

## Greedy Mathematical Approach
The most optimal solution is a greedy, mathematical approach that constructs the longest string based on a few key observations about how the string blocks can be combined. By understanding the roles of each type of string, we can derive a simple formula to calculate the maximum length directly without any recursion or complex data structures.
**Time:** O(1) - The solution consists of a few arithmetic operations, which are independent of the input sizes `x`, `y`, and `z`. · **Space:** O(1) - The calculation uses only a few variables, requiring constant extra space.
**Pros:** Extremely efficient with constant time and space complexity.; Simple and elegant implementation.
**Cons:** The correctness relies on a greedy insight that might not be immediately obvious.
### Explanation
This approach is based on the insight that we can separate the problem into two parts: using the "AB" strings and using the "AA"/"BB" strings.

1.  **"AB" strings**: An "AB" string is very flexible. It starts with 'A' and ends with 'B'. Placing it never creates a "AAA" or "BBB" substring, regardless of its neighbors. For example, `...A` + `AB` gives `...AAB`, and `AB` + `B...` gives `ABB...`. Therefore, we can greedily use all `z` available "AB" strings. This gives us a length of `2 * z`.

2.  **"AA" and "BB" strings**: These strings are restrictive. An "AA" cannot be placed next to another "AA", and similarly for "BB". This forces an alternating pattern. We can form the longest possible chain of these by using as many as possible. If we have `x` "AA"s and `y` "BB"s, we can always form an alternating chain using `min(x, y)` of each. If `x` and `y` are unequal, we can add one more block from the more numerous type at one end of the chain. For example, if `x > y`, we can form `AABBAA...BBAA`, using `y` "BB"s and `y+1` "AA"s. This logic leads to a simple calculation: if `x == y`, we use `2*x` blocks for a length of `4*x`; if `x != y`, we use `2*min(x,y) + 1` blocks for a length of `4*min(x,y) + 2`.

The total maximum length is the sum of these two parts.
### Algorithm
*   Recognize that all `z` strings of type "AB" can be used without creating forbidden substrings. They can be interspersed anywhere. This contributes `2 * z` to the total length.
*   Focus on the "AA" and "BB" strings. To avoid "AAA" and "BBB", they must be placed in an alternating sequence (e.g., `AABBAA...` or `BBAABB...`).
*   The number of "AA" and "BB" blocks in such a chain can differ by at most one.
*   **Case 1: `x == y`**. We can use all `x` "AA"s and all `y` "BB"s by perfectly alternating them (e.g., `AABBAA...BB`). This contributes `2 * (x + y)` or `4 * x` to the length.
*   **Case 2: `x != y`**. We can use `min(x, y)` blocks of each type to form pairs, and then add one extra block of the more numerous type. For example, if `x > y`, we can use `y` "BB"s and `y+1` "AA"s. The total number of blocks used is `2 * min(x, y) + 1`. This contributes `2 * (2 * min(x, y) + 1)` to the length.
*   The final result is the sum of the length from the "AB" strings and the length from the "AA"/"BB" chain.

# Solutions
### Java

```java
class Solution {
public
  int longestString(int x, int y, int z) {
    if (x < y) {
      return (x * 2 + z + 1) * 2;
    }
    if (x > y) {
      return (y * 2 + z + 1) * 2;
    }
    return (x + y + z) * 2;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestString(int x, int y, int z) {
    if (x < y) {
      return (x * 2 + z + 1) * 2;
    }
    if (x > y) {
      return (y * 2 + z + 1) * 2;
    }
    return (x + y + z) * 2;
  }
};

```

### Python

```python
class Solution:
    def longestString(self, x: int, y: int, z: int) -> int: if x < y: return (x * 2 + z + 1) * 2 if x > y: return (y * 2 + z + 1) * 2 return (x + y + z) * 2

```