<p>You are playing a variation of the game Zuma.</p>

<p>In this variation of Zuma, there is a <strong>single row</strong> of colored balls on a board, where each ball can be colored red <code>&#39;R&#39;</code>, yellow <code>&#39;Y&#39;</code>, blue <code>&#39;B&#39;</code>, green <code>&#39;G&#39;</code>, or white <code>&#39;W&#39;</code>. You also have several colored balls in your hand.</p>

<p>Your goal is to <strong>clear all</strong> of the balls from the board. On each turn:</p>

<ul>
	<li>Pick <strong>any</strong> ball from your hand and insert it in between two balls in the row or on either end of the row.</li>
	<li>If there is a group of <strong>three or more consecutive balls</strong> of the <strong>same color</strong>, remove the group of balls from the board.
	<ul>
		<li>If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.</li>
	</ul>
	</li>
	<li>If there are no more balls on the board, then you win the game.</li>
	<li>Repeat this process until you either win or do not have any more balls in your hand.</li>
</ul>

<p>Given a string <code>board</code>, representing the row of balls on the board, and a string <code>hand</code>, representing the balls in your hand, return <em>the <strong>minimum</strong> number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return </em><code>-1</code>.</p>

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

<pre>
<strong>Input:</strong> board = &quot;WRRBBW&quot;, hand = &quot;RB&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> It is impossible to clear all the balls. The best you can do is:
- Insert &#39;R&#39; so the board becomes WRR<u>R</u>BBW. W<u>RRR</u>BBW -&gt; WBBW.
- Insert &#39;B&#39; so the board becomes WBB<u>B</u>W. W<u>BBB</u>W -&gt; WW.
There are still balls remaining on the board, and you are out of balls to insert.</pre>

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

<pre>
<strong>Input:</strong> board = &quot;WWRRBBWW&quot;, hand = &quot;WRBRW&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make the board empty:
- Insert &#39;R&#39; so the board becomes WWRR<u>R</u>BBWW. WW<u>RRR</u>BBWW -&gt; WWBBWW.
- Insert &#39;B&#39; so the board becomes WWBB<u>B</u>WW. WW<u>BBB</u>WW -&gt; <u>WWWW</u> -&gt; empty.
2 balls from your hand were needed to clear the board.
</pre>

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

<pre>
<strong>Input:</strong> board = &quot;G&quot;, hand = &quot;GGGGG&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make the board empty:
- Insert &#39;G&#39; so the board becomes G<u>G</u>.
- Insert &#39;G&#39; so the board becomes GG<u>G</u>. <u>GGG</u> -&gt; empty.
2 balls from your hand were needed to clear the board.
</pre>

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

<ul>
	<li><code>1 &lt;= board.length &lt;= 16</code></li>
	<li><code>1 &lt;= hand.length &lt;= 5</code></li>
	<li><code>board</code> and <code>hand</code> consist of the characters <code>&#39;R&#39;</code>, <code>&#39;Y&#39;</code>, <code>&#39;B&#39;</code>, <code>&#39;G&#39;</code>, and <code>&#39;W&#39;</code>.</li>
	<li>The initial row of balls on the board will <strong>not</strong> have any groups of three or more consecutive balls of the same color.</li>
</ul>

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        '''
        * insert all the balls on a board 
            * If the board has two or balls insert between the two balls
            * If the board has one ball, insert at the end..
        * if there's 3 or more of same color.. group gets removed
        * to win, make the board empty
        ======
        * 1 <= board.length <= 16 ; so a recursive approach could work; => works! 
        * try every insertion at every index and remove consecutive blocks of same color 
        '''
        def clean(board_, idx): # go previous as long as it's the same char; llikewise go forward from idx.. that should give the total chars with same color
            if not board_ or idx < 0: return board_
            l = r = idx
            for i in range(idx, -1, -1): 
                if board_[i] != board_[idx]: break 
                l = i 

            for i in range(idx, len(board_)): 
                if board_[i] != board_[idx]: break
                r = i

            num_elems = r - l + 1
            if num_elems >= 3: 
                return clean(board_[:l] + board_[r + 1:], l - 1) # continue removing as much as I can.. 
            else: 
                return board_ # nothing or less than 3 so can't remove..  

        @cache
        def helper(hand, board):
            if not board: return 0 # base case -> won; board empty
            if not hand: return inf # board is not empty but I ran out of balls in my hand.. 
            moves = inf
            for idx, color in enumerate(hand): # what do I have in my hand
                for insert_at in range(len(board)):  # where to insert it? 
                    if board[insert_at] == color or (insert_at > 0 and board[insert_at - 1] == board[insert_at] and color != board[insert_at]): # exact color match at insert index or something is on the left and it's of the same color as insert index and the current color in hand is not the same.. 
                        inserted_board = board[:insert_at] + color + board[insert_at:]
                        ### pop all the 3 or more consecutives: 
                        next_round_board = clean(inserted_board, insert_at)
                        if next_round_board == "": 
                            return 1 # base case: stop; won!
                        
                        next_round_hand = hand[:idx] + hand[idx + 1:]
                        moves = min(moves, 1 + helper(next_round_hand, next_round_board))
            return moves

        ans = helper(hand, board)
        return ans if ans != inf else -1
29700