<p>You are given three integers <code>x</code>, <code>y</code>, and <code>z</code>.</p>

<p>You have <code>x</code> strings equal to <code>&quot;AA&quot;</code>, <code>y</code> strings equal to <code>&quot;BB&quot;</code>, and <code>z</code> strings equal to <code>&quot;AB&quot;</code>. 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 <code>&quot;AAA&quot;</code> or <code>&quot;BBB&quot;</code> as a substring.</p>

<p>Return <em>the maximum possible length of the new string</em>.</p>

<p>A <b>substring</b> is a contiguous <strong>non-empty</strong> sequence of characters within a string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> x = 2, y = 5, z = 1
<strong>Output:</strong> 12
<strong>Explanation: </strong>We can concactenate the strings &quot;BB&quot;, &quot;AA&quot;, &quot;BB&quot;, &quot;AA&quot;, &quot;BB&quot;, and &quot;AB&quot; in that order. Then, our new string is &quot;BBAABBAABBAB&quot;. 
That string has length 12, and we can show that it is impossible to construct a string of longer length.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> x = 3, y = 2, z = 2
<strong>Output:</strong> 14
<strong>Explanation:</strong> We can concactenate the strings &quot;AB&quot;, &quot;AB&quot;, &quot;AA&quot;, &quot;BB&quot;, &quot;AA&quot;, &quot;BB&quot;, and &quot;AA&quot; in that order. Then, our new string is &quot;ABABAABBAABBAA&quot;. 
That string has length 14, and we can show that it is impossible to construct a string of longer length.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= x, y, z &lt;= 50</code></li>
</ul>

"""

Better is 4D Dp maintain state for last and each integer of x, y,z
if integer is greater than 0 and last != undesired max = 2 + helper(-2, state)

TC : O(XYZ)
SC : (4XYZ)

Optimal
Place z strings all and place min(x,y) and plus if x != y
TC : O(1)
SC : O(1)

"""


class Solution:

    def __init__(self):
        self.dp = None


    def longestString(self, x: int, y: int, z: int) -> int:
        # intilize 4d dp with 4*(x+1) * (y+1) * (z+1)
        self.dp = [ [ [ [0]*4 for _ in range(z+1)   ] for _ in range(y+1)  ] for _ in range(x+1)   ]

        return self.helper(x, y, z, 0)

        # 0 None
        # 1 AA
        # 2 BB
        # 3 AB

    def helper(self,x,y,z,last):

        if self.dp[x][y][z][last] != 0:
            return self.dp[x][y][z][last]
        
        res = 0

        if x > 0 and last != 1:
            res = max(res, 2 + self.helper(x-1, y, z, 1))
        
        if y > 0 and last < 2:
            res = max(res, 2 + self.helper(x, y-1, z, 2))
        
        if z > 0 and last != 1:
            res = max(res, 2 + self.helper(x, y, z-1,3))

        self.dp[x][y][z][last] = res
        return res




        """
        Approach 1


        mn = min(x,y)

        zLen = z*2
        single = 1 if x != y else 0
        
        return mn*4 + (single * 2) + zLen
        """
        
30200