Construct the Longest New String
MedPrompt
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
3 approaches with complexity analysis and trade-offs.
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".
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. lastBlockcan 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")andsolve(x, y, z - 1, "AB"), and take the maximum result.
- If the last block was "AA", the next must be "BB". We make a recursive call
- The main function initiates three separate recursive chains, one for each possible starting block ("AA", "BB", "AB"), and returns the maximum length found.
Walkthrough
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.
Complexity
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.
Trade-offs
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.
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.
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 thelastBlockType. - 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.
Walkthrough
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.
Complexity
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.
Trade-offs
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.
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.
Algorithm
- Recognize that all
zstrings of type "AB" can be used without creating forbidden substrings. They can be interspersed anywhere. This contributes2 * zto 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...orBBAABB...). - The number of "AA" and "BB" blocks in such a chain can differ by at most one.
- Case 1:
x == y. We can use allx"AA"s and ally"BB"s by perfectly alternating them (e.g.,AABBAA...BB). This contributes2 * (x + y)or4 * xto the length. - Case 2:
x != y. We can usemin(x, y)blocks of each type to form pairs, and then add one extra block of the more numerous type. For example, ifx > y, we can usey"BB"s andy+1"AA"s. The total number of blocks used is2 * min(x, y) + 1. This contributes2 * (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.
Walkthrough
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.
-
"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+ABgives...AAB, andAB+B...givesABB.... Therefore, we can greedily use allzavailable "AB" strings. This gives us a length of2 * z. -
"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 andy"BB"s, we can always form an alternating chain usingmin(x, y)of each. Ifxandyare unequal, we can add one more block from the more numerous type at one end of the chain. For example, ifx > y, we can formAABBAA...BBAA, usingy"BB"s andy+1"AA"s. This logic leads to a simple calculation: ifx == y, we use2*xblocks for a length of4*x; ifx != y, we use2*min(x,y) + 1blocks for a length of4*min(x,y) + 2.
The total maximum length is the sum of these two parts.
Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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) * 2Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.