1
class Solution:
2
    def findMinStep(self, board: str, hand: str) -> int:
3

4
        # start from i and remove continues ball
5
        def remove_same(s, i):
6
            if i < 0:
7
                return s
8

9
            left = right = i
10
            while left > 0 and s[left - 1] == s[i]:
11
                left -= 1
12
            while right + 1 < len(s) and s[right + 1] == s[i]:
13
                right += 1
14

15
            length = right - left + 1
16
            if length >= 3:
17
                new_s = s[:left] + s[right + 1 :]
18
                return remove_same(new_s, left - 1)
19
            else:
20
                return s
21

22
        hand = "".join(sorted(hand))
23

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

28
        while q:
29
            curr_board, curr_hand, step = q.popleft()
30
            for i in range(len(curr_board) + 1):
31
                for j in range(len(curr_hand)):
32
                    # skip the continue balls in hand
33
                    if j > 0 and curr_hand[j] == curr_hand[j - 1]:
34
                        continue
35

36
                    # only insert at the begin of continue balls in board
37
                    if (
38
                        i > 0 and curr_board[i - 1] == curr_hand[j]
39
                    ):  # left side same color
40
                        continue
41

42
                    pick = False
43
                    # 1. same color with right
44
                    # 2. left and right are same but pick is different
45
                    if i < len(curr_board) and curr_board[i] == curr_hand[j]:
46
                        pick = True
47
                    if (
48
                        0 < i < len(curr_board)
49
                        and curr_board[i - 1] == curr_board[i]
50
                        and curr_board[i] != curr_hand[j]
51
                    ):
52
                        pick = True
53

54
                    if pick:
55
                        new_board = remove_same(
56
                            curr_board[:i] + curr_hand[j] + curr_board[i:], i
57
                        )
58
                        new_hand = curr_hand[:j] + curr_hand[j + 1 :]
59
                        if not new_board:
60
                            return step + 1
61
                        if (new_board, new_hand) not in visited:
62
                            q.append((new_board, new_hand, step + 1))
63
                            visited.add((new_board, new_hand))
64

65
        return -1