Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/488.html
488. Zuma Game
Level
Hard
Description
Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.
Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.
Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output 1.
Example 1:
Input: board = “WRRBBW”, hand = “RB”
Output: 1
Explanation: WRRBBW > WRR[R]BBW > WBBW > WBB[B]W > WW
Example 2:
Input: board = “WWRRBBWW”, hand = “WRBRW”
Output: 2
Explanation: WWRRBBWW > WWRR[R]BBWW > WWBBWW > WWBB[B]WW > WWWW > empty
Example 3:
Input: board = “G”, hand = “GGGGG”
Output: 2
Explanation: G > G[G] > GG[G] > empty
Example 4:
Input: board = “RBYYBBRRB”, hand = “YRBGB”
Output: 3
Explanation: RBYYBBRRB > RBYY[Y]BBRRB > RBBBRRB > RRRB > B > B[B] > BB[B] > empty
Constraints:
 You may assume that the initial row of balls on the table wont have any 3 or more consecutive balls with the same color.
 The number of balls on the table won’t exceed 16, and the string represents these balls is called “board” in the input.
 The number of balls in your hand won’t exceed 5, and the string represents these balls is called “hand” in the input.
 Both input strings will be nonempty and only contain characters ‘R’,’Y’,’B’,’G’,’W’.
Solution
Use backtrack with memorization. First loop over hand
to obtain the number of balls of each color in hand
. Then call the backtrack method.
In the backtrack method, first remove three or more consecutive balls with the same color from board
. The remove operation is executed several times over board
until no more balls can be removed. Then return 0 if board
is empty. Use board
concatenated with the string representation of each color’s count as the key to loop up the memorization. If the key exists, obtain the number of insertions from the key and return.
For each available color in hand
, try each insertion position in board
and obtain the minimum number of insertions, and update the memorization. If the empty string is reached, then it is possible to remove all the balls, and return the minimum number of insertions. Otherwise, return 1.

class Solution { public int findMinStep(String board, String hand) { Map<Character, Integer> colorIdMap = new HashMap<Character, Integer>(); Map<Integer, Character> idColorMap = new HashMap<Integer, Character>(); String colors = "RYBGW"; for (int id = 0; id < 5; id++) { char color = colors.charAt(id); colorIdMap.put(color, id); idColorMap.put(id, color); } Map<String, Integer> memo = new HashMap<String, Integer>(); int[] hands = new int[5]; int handLength = hand.length(); for (int i = 0; i < handLength; i++) { char c = hand.charAt(i); int index = colorIdMap.get(c); hands[index]++; } return backtrack(board, hands, idColorMap, memo); } public int backtrack(String board, int[] hands, Map<Integer, Character> idColorMap, Map<String, Integer> memo) { board = removeSame(board); if (board.length() == 0) return 0; String key = board + Arrays.toString(hands); if (memo.containsKey(key)) return memo.get(key); int insertions = 1; int handsLength = hands.length, boardLength = board.length(); for (int i = 0; i < handsLength; i++) { if (hands[i] != 0) { char color = idColorMap.get(i); hands[i]; for (int j = 0; j <= boardLength; j++) { String newBoard = board.substring(0, j) + color + board.substring(j); int nextInsertions = backtrack(newBoard, hands, idColorMap, memo); if (nextInsertions != 1) { if (insertions == 1) insertions = nextInsertions + 1; else insertions = Math.min(insertions, nextInsertions + 1); } } hands[i]++; } } memo.put(key, insertions); return insertions; } public String removeSame(String board) { StringBuffer sb = new StringBuffer(board); int length = sb.length(); boolean flag = true; while (flag) { int left = length  2, right = length  1; while (left >= 0) { if (sb.charAt(left) == sb.charAt(right)) left; else { if (right  left >= 3) { sb.delete(left + 1, right + 1); right = left; left; } else right = left; } } if (right  left >= 3) sb.delete(left + 1, right + 1); int curLength = sb.length(); if (curLength == length) flag = false; else length = curLength; } return sb.toString(); } }

class Solution: def findMinStep(self, board: str, hand: str) > int: def remove(s): while len(s): next = re.sub(r'B{3,}G{3,}R{3,}W{3,}Y{3,}', '', s) if len(next) == len(s): break s = next return s visited = set() q = deque([(board, hand)]) while q: state, balls = q.popleft() if not state: return len(hand)  len(balls) for ball in set(balls): b = balls.replace(ball, '', 1) for i in range(1, len(state) + 1): s = state[:i] + ball + state[i:] s = remove(s) if s not in visited: visited.add(s) q.append((s, b)) return 1 ############ class Solution(object): def findMinStep(self, board, hand): """ :type board: str :type hand: str :rtype: int """ def dfs(line, balls, visited): line = reduceLine(line) if (line, balls) in visited: return visited[line, balls] if len(line) == 0: return len(hand)  len(balls) if len(balls) == 0: return float("inf") res = float("inf") for i in range(len(balls)): for j in range(len(line) + 1): if j == 0 and line[0] != balls[i]: continue elif j == len(line) and line[1] != balls[i]: continue elif 0 < j < len(line) and balls[i] != line[j  1] and balls[i] != line[j]: continue res = min(res, dfs(line[:j] + balls[i] + line[j:], balls[:i] + balls[i + 1:], visited)) visited[line, balls] = res return res def reduceLine(line): def reducer(line): if len(line) < 3: return line ret = [] dp = [1] * len(line) pre = line[1] count = 1 for i in reversed(range(len(line)  1)): if line[i] == pre: count += 1 else: pre = line[i] count = 1 dp[i] = count i = 0 while i < len(line): if dp[i] >= 3: i += dp[i] else: ret.extend(line[i:i + dp[i]]) i += dp[i] return "".join(ret) if len(line) < 3: return line ans = line for _ in range(len(line) / 3): ans = reducer(ans) return ans visited = {} ret = dfs(board, "".join(sorted(hand)), visited) return ret if ret != float("inf") else 1