<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>

import time

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        # only insert next to the same letter
        # ~ 5! possible insertion orders
            # O(16) possible insertion points
        hand = ''.join(sorted(hand))
        @lru_cache(None)
        def clean(board):
            # print('clean', board)
            last = None
            cnt = 1
            ret = []
            changed = False
            for i in range(len(board)):
                if board[i] == last:
                    cnt += 1
                else:
                    if last and cnt < 3:
                        for _ in range(cnt):
                            ret.append(last)
                    elif cnt >= 3:
                        changed = True
                    cnt = 1
                last = board[i]
            if last and cnt < 3:
                for _ in range(cnt):
                    ret.append(last)
            elif cnt >= 3:
                changed = True

            # print('finished clean', ret)
            if changed:
                return clean(tuple(ret))
            return tuple(ret)

        def remove_same(s, i):
            if i < 0:
                return s
            
            left = right = i
            while left > 0 and s[left-1] == s[i]:
                left -= 1
            while right+1 < len(s) and s[right+1] == s[i]:
                right += 1
            
            length = right - left + 1
            if length >= 3:
                new_s = s[:left] + s[right+1:]
                return remove_same(new_s, left-1)
            else:
                return s
        # def clean(s):
            # return remove_same(s, 0)
        # first iter:
            # creates 5*16 possible states
        # 2nd iter:
            # creates ~5*16 possible states
        @lru_cache(None)
        def rec(seen, board):
            if board == ():
                return 0
            best = math.inf
            # 5
            for i in range(len(hand)):
                if (1<<i) & seen:
                    continue
                # if i > 0 and hand[i-1] == hand[i] and ((1<<(i-1)) & seen):
                #     continue
                h = hand[i]
                # 16
                for j in range(len(board)):
                    # inner loop is ~16
                    # inserting at any point in a line is equivalent
                    if j-1 >= 0 and board[j] == board[j-1] and board[j] == h:
                        continue
                    if board[j] != h:
                        # only worth inserting into someone that's not us IF we're inserting in the middle of them
                        if j-1 < 0 or board[j-1] != board[j]:
                            continue
                    new_board = list(board)
                    new_board.insert(j, h)
                    new_board = remove_same(tuple(new_board), j)
                    # print('inserted',j, h, new_board)
                    best = min(best, 1+rec(seen|(1<<i), new_board))
            return best
        v = 0
        # insertion order does matter...
        # @lru_cache(None)
        # # 5*16, each call is 16*16
        # def rec(i, board):
        #     if board == ():
        #         return 0
        #     if i >= len(hand):
        #         return math.inf
        #     best = math.inf
        #     h = hand[i]
        #     # 16
        #     for j in range(len(board)):
        #         t = time.time()
        #         # inner loop is ~16
        #         # inserting at any point in a line is equivalent
        #         if j-1 >= 0 and board[j] == board[j-1] and board[j] == h:
        #             continue
        #         new_board = list(board)
        #         new_board.insert(j, h)
        #         new_board = clean(tuple(new_board))
        #         # print('cleaning',t2-t)
        #         # print('inserted',j, h, new_board)
        #         t2 = time.time()
        #         nonlocal v
        #         v = max(t2-t,v)
        #         best = min(best, 1+rec(i+1, new_board))
        #     # don't insert at all
        #     best = min(best, rec(i+1, board))
        #     return best
        ret = rec(0, tuple(board))
        print(v)
        if ret == math.inf:
            return -1
        return ret

# class Solution:
#     def findMinStep(self, board: str, hand: str) -> int:
        
#         # start from i and remove continues ball
#         def remove_same(s, i):
#             if i < 0:
#                 return s
            
#             left = right = i
#             while left > 0 and s[left-1] == s[i]:
#                 left -= 1
#             while right+1 < len(s) and s[right+1] == s[i]:
#                 right += 1
            
#             length = right - left + 1
#             if length >= 3:
#                 new_s = s[:left] + s[right+1:]
#                 return remove_same(new_s, left-1)
#             else:
#                 return s



#         hand = "".join(sorted(hand))

#         # board, hand and step
#         q = collections.deque([(board, hand, 0)])
#         visited = set([(board, hand)])

#         while q:
#             curr_board, curr_hand, step = q.popleft()
#             for i in range(len(curr_board)+1):
#                 for j in range(len(curr_hand)):
#                     # skip the continue balls in hand
#                     if j > 0 and curr_hand[j] == curr_hand[j-1]:
#                         continue
                    
#                     # only insert at the begin of continue balls in board
#                     if i > 0 and curr_board[i-1] == curr_hand[j]: # left side same color
#                         continue
                    
#                     pick = False
#                     # 1. same color with right
#                     # 2. left and right are same but pick is different
#                     if i < len(curr_board) and curr_board[i] == curr_hand[j]:
#                         pick = True
#                     if 0<i<len(curr_board) and curr_board[i-1] == curr_board[i] and curr_board[i] != curr_hand[j]:
#                         pick = True
                    
#                     if pick:
#                         new_board = remove_same(curr_board[:i] + curr_hand[j] + curr_board[i:], i)
#                         new_hand = curr_hand[:j] + curr_hand[j+1:]
#                         if not new_board:
#                             return step + 1
#                         if (new_board, new_hand) not in visited:
#                             q.append((new_board, new_hand, step+1))
#                             visited.add((new_board, new_hand))

#         return -1
37700