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.
Input: x =2, y =5, z =1Output: 12Explanation: 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.
Input: x =3, y =2, z =2Output: 14Explanation: 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.
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.
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).