# Zuma Game **Difficulty:** HARD [External](https://leetcode.com/problems/zuma-game) Canonical: https://scaleengineer.com/dsa/problems/zuma-game **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization) **Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** String, Stack **Companies:** [Baidu](https://scaleengineer.com/companies/baidu) --- ## Problem You are playing a variation of the game Zuma. In this variation of Zuma, there is a **single row** of colored balls on a board, where each ball can be colored red `'R'`, yellow `'Y'`, blue `'B'`, green `'G'`, or white `'W'`. You also have several colored balls in your hand. Your goal is to **clear all** of the balls from the board. On each turn: * Pick **any** ball from your hand and insert it in between two balls in the row or on either end of the row. * If there is a group of **three or more consecutive balls** of the **same color**, remove the group of balls from the board. * 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. * If there are no more balls on the board, then you win the game. * Repeat this process until you either win or do not have any more balls in your hand. Given a string `board`, representing the row of balls on the board, and a string `hand`, representing the balls in your hand, return _the **minimum** 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_ `-1`. **Example 1:** **Input:** board = "WRRBBW", hand = "RB" **Output:** -1 **Explanation:** It is impossible to clear all the balls. The best you can do is: - Insert 'R' so the board becomes WRRRBBW. WRRRBBW -> WBBW. - Insert 'B' so the board becomes WBBBW. WBBBW -> WW. There are still balls remaining on the board, and you are out of balls to insert. **Example 2:** **Input:** board = "WWRRBBWW", hand = "WRBRW" **Output:** 2 **Explanation:** To make the board empty: - Insert 'R' so the board becomes WWRRRBBWW. WWRRRBBWW -> WWBBWW. - Insert 'B' so the board becomes WWBBBWW. WWBBBWW -> WWWW -> empty. 2 balls from your hand were needed to clear the board. **Example 3:** **Input:** board = "G", hand = "GGGGG" **Output:** 2 **Explanation:** To make the board empty: - Insert 'G' so the board becomes GG. - Insert 'G' so the board becomes GGG. GGG -> empty. 2 balls from your hand were needed to clear the board. **Constraints:** * `1 <= board.length <= 16` * `1 <= hand.length <= 5` * `board` and `hand` consist of the characters `'R'`, `'Y'`, `'B'`, `'G'`, and `'W'`. * The initial row of balls on the board will **not** have any groups of three or more consecutive balls of the same color. # Approaches ## Brute-Force Breadth-First Search (BFS) This approach explores all possible game states using a Breadth-First Search (BFS). BFS is suitable here because we are looking for the *minimum* number of balls, which corresponds to the shortest path in the state graph. A state consists of the current board and the balls in hand. We start from the initial state and explore all possible moves level by level. Each level in the BFS tree corresponds to using one additional ball from the hand. A `visited` set is crucial to avoid re-processing the same state. **Time:** O(S * M * L * L), where S is the number of states, M is the hand size, and L is the board length. Generating next states involves iterating through the hand (M), insertion points (L), and updating the board (which can take O(L) or O(L^2)). The number of states S can be enormous, making this approach impractical. · **Space:** O(S * L), where S is the number of unique states and L is the maximum possible length of the board string. The space required for the queue and visited set can be very large. **Pros:** Guaranteed to find the minimum number of balls if a solution exists.; Conceptually straightforward to understand. **Cons:** Extremely high time and space complexity due to the massive state space.; Likely to result in a 'Time Limit Exceeded' error for the given constraints. ### Explanation The brute-force BFS systematically checks every outcome. We define a state by the tuple `(board, hand)`. Starting with the initial board and hand, we generate all states reachable in one move (using one ball). Then, from those states, we generate all states reachable in two moves, and so on. Because BFS explores layer by layer, the first time we encounter a state with an empty board, we are guaranteed to have used the minimum number of balls. To implement this, we use a queue to store the states to visit. To avoid infinite loops and redundant work, we use a `Set` to keep track of states we've already seen. The hand can be represented as a sorted string to ensure that different permutations of the same set of balls are treated as the same state. ```java import java.util.*; class Solution { public int findMinStep(String board, String hand) { Queue> queue = new LinkedList<>(); Set visited = new HashSet<>(); char[] handChars = hand.toCharArray(); Arrays.sort(handChars); String sortedHand = new String(handChars); queue.offer(new Pair<>(board, sortedHand)); visited.add(board + "#" + sortedHand); int steps = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { Pair current = queue.poll(); String currentBoard = current.getKey(); String currentHand = current.getValue(); if (currentBoard.isEmpty()) { return steps; } for (int j = 0; j < currentHand.length(); j++) { // Avoid using the same ball multiple times in one step if (j > 0 && currentHand.charAt(j) == currentHand.charAt(j - 1)) { continue; } char ball = currentHand.charAt(j); String nextHand = currentHand.substring(0, j) + currentHand.substring(j + 1); for (int k = 0; k <= currentBoard.length(); k++) { StringBuilder sb = new StringBuilder(currentBoard); sb.insert(k, ball); String nextBoard = update(sb.toString()); String stateKey = nextBoard + "#" + nextHand; if (!visited.contains(stateKey)) { visited.add(stateKey); queue.offer(new Pair<>(nextBoard, nextHand)); } } } } steps++; } return -1; } private String update(String board) { String currentBoard = board; while (true) { int start = -1, end = -1; for (int i = 0; i < currentBoard.length(); ) { int j = i; while (j < currentBoard.length() && currentBoard.charAt(j) == currentBoard.charAt(i)) { j++; } if (j - i >= 3) { start = i; end = j; break; } i = j; } if (start != -1) { currentBoard = currentBoard.substring(0, start) + currentBoard.substring(end); } else { break; } } return currentBoard; } } // Note: Pair class would need to be defined or use an alternative like an array. ``` ### Algorithm - **State Representation**: A state is defined by the current configuration of the board (a string) and the balls remaining in the hand (represented as a sorted string or a frequency map). - **Queue**: A queue is used to perform a level-order traversal of the state space. It stores pairs of `(board, hand)`. - **Visited Set**: A set stores visited states `(board, hand)` to prevent cycles and redundant computations. - **Initialization**: Start with a queue containing the initial state `(initial_board, initial_hand)` and a `visited` set containing the same. The number of balls used (`steps`) is initialized to 0. - **BFS Traversal**: 1. Loop as long as the queue is not empty. 2. In each iteration, process all states at the current level (same `steps`). 3. For each state `(current_board, current_hand)` dequeued: - If `current_board` is empty, a solution is found. Return `steps`. - Generate all possible next states by trying to insert each ball from `current_hand` into every possible position on `current_board`. - For each insertion, update the board by removing any groups of three or more balls (handling chain reactions). - If a new state `(new_board, new_hand)` has not been visited, add it to the queue and the `visited` set. 4. After processing a full level, increment `steps`. - **Termination**: If the queue becomes empty and no solution is found, it's impossible to clear the board. Return -1. ## DFS with Memoization and Strategic Pruning A more efficient method is to use a recursive Depth-First Search (DFS) combined with memoization. The key insight is to prune the vast search space by changing the strategy. Instead of blindly inserting balls anywhere, we focus on a more purposeful action: completing a group of three. For every consecutive group of one or two balls on the board, we check if we have the necessary balls in our hand to make it a group of three. If we do, we commit to this move, update the board (which might cause chain reactions), and recursively solve the subproblem for the new board and reduced hand. Memoization is essential to store the results of subproblems `(board, hand)` to avoid re-computing them, effectively turning the recursion into a dynamic programming solution. **Time:** The worst-case complexity is difficult to determine precisely but is much better than brute-force. It depends on the number of reachable, distinct states. With a small hand size (M <= 5) and a limited board length (N <= 16), the number of relevant states explored is manageable. The branching factor is the number of groups on the board (at most L), and recursion depth is at most M. · **Space:** O(S * L + M*L), where S is the number of states stored in the memoization table, L is the max board length, and M is the recursion depth (at most hand size). The space is dominated by the memoization table and the recursion stack. **Pros:** Significantly more efficient than brute-force due to intelligent pruning of the search space.; Feasible for the given constraints because it avoids exploring many useless moves.; Memoization prevents re-computation of the same subproblems. **Cons:** The implementation is more complex than the brute-force approach.; The correctness relies on the heuristic that it's always optimal to use balls to complete an existing group on the board. ### Explanation This optimized DFS approach works by focusing on the goal: clearing groups of three. The state is defined by the board string and the count of each colored ball in hand. The `dfs` function explores possibilities by trying to clear each existing group on the board. For a group of size 1 (e.g., `B`), it needs 2 balls. For a group of size 2 (e.g., `RR`), it needs 1 ball. If the hand contains the required balls, we simulate this move. This involves removing the group from the board, which might cause adjacent balls of the same color to merge and form a new group of three or more. This chain reaction is handled by an `update` helper function that repeatedly scans and shrinks the board until no more groups of three exist. The result of the recursive call is then used to find the minimum balls needed. Memoization is critical for performance. We store the result for each `(board, handCount)` state in a map. Before any computation, we check the map, and after computing a result, we store it. This prevents solving the same subproblem multiple times. ```java import java.util.*; class Solution { private Map memo; private final int MAX_BALLS = 6; // A value larger than hand.length() public int findMinStep(String board, String hand) { int[] handCount = new int[26]; for (char c : hand.toCharArray()) { handCount[c - 'A']++; } memo = new HashMap<>(); int result = dfs(board, handCount); return result >= MAX_BALLS ? -1 : result; } private int dfs(String board, int[] handCount) { if (board.isEmpty()) { return 0; } String key = board + "#" + Arrays.toString(handCount); if (memo.containsKey(key)) { return memo.get(key); } int res = MAX_BALLS; for (int i = 0; i < board.length(); ) { int j = i; while (j < board.length() && board.charAt(j) == board.charAt(i)) { j++; } // Group is board[i..j-1] int groupSize = j - i; char color = board.charAt(i); int needed = 3 - groupSize; if (handCount[color - 'A'] >= needed) { handCount[color - 'A'] -= needed; String nextBoard = update(board.substring(0, i) + board.substring(j)); int subProblemRes = dfs(nextBoard, handCount); if (subProblemRes < MAX_BALLS) { res = Math.min(res, needed + subProblemRes); } handCount[color - 'A'] += needed; // Backtrack } i = j; } memo.put(key, res); return res; } private String update(String board) { String currentBoard = board; while (true) { int start = -1, end = -1; for (int i = 0; i < currentBoard.length(); ) { int j = i; while (j < currentBoard.length() && currentBoard.charAt(j) == currentBoard.charAt(i)) { j++; } if (j - i >= 3) { start = i; end = j; break; } i = j; } if (start != -1) { currentBoard = currentBoard.substring(0, start) + currentBoard.substring(end); } else { break; } } return currentBoard; } } ``` ### Algorithm - **State Representation**: A state is defined by the `board` string and a frequency map of the balls in `hand`. - **Memoization**: A hash map is used to store the computed minimum balls for each state `(board, hand)` to avoid redundant calculations. The key can be a unique string representation of the state. - **Initial Pruning**: Before starting the search, perform a quick check. For each color, if there are balls of that color on the board, the total count of balls of that color (on board + in hand) must be at least 3. If not, a solution is impossible. - **Recursive Function `dfs(board, handCount)`**: 1. **Update Board**: First, apply the Zuma rule to the current `board` to clear any existing groups of 3 or more. This handles chain reactions that occur without using new balls. 2. **Base Case**: If the updated `board` is empty, return 0. 3. **Memoization Check**: If the current state is in the memoization table, return the stored value. 4. **Recursive Exploration**: Initialize `min_balls = infinity`. Iterate through the board to find all consecutive groups of same-colored balls (e.g., `R` or `BB`). - For each group of size `k`, calculate the `needed` balls from the hand to make it a group of 3 (i.e., `3 - k`). - If the hand has enough `needed` balls of that color: - Temporarily update the hand count. - Form a new board by removing the current group. - Recursively call `dfs` with the new board and hand. - If the recursive call returns a valid result, update `min_balls` with `needed + result`. - Backtrack by restoring the hand count. 5. **Memoize and Return**: Store `min_balls` in the memoization table for the current state and return it. - **Final Result**: The main function calls `dfs` with the initial state. If the result is infinity, return -1; otherwise, return the result. # Solutions ### Java ```java class Solution { public int findMinStep(String board, String hand) { final Zuma zuma = Zuma.create(board, hand); final HashSet visited = new HashSet<>(); final ArrayList init = new ArrayList<>(); visited.add(zuma.board()); init.add(zuma); return bfs(init, 0, visited); } private int bfs(ArrayList curr, int k, HashSet visited) { if (curr.isEmpty()) { return -1; } final ArrayList next = new ArrayList<>(); for (Zuma zuma : curr) { ArrayList neib = zuma.getNextLevel(k, visited); if (neib == null) { return k + 1; } next.addAll(neib); } return bfs(next, k + 1, visited); } } record Zuma(long board, long hand) { public static Zuma create(String boardStr, String handStr) { return new Zuma(Zuma.encode(boardStr, false), Zuma.encode(handStr, true)); } public ArrayList getNextLevel(int depth, HashSet visited) { final ArrayList next = new ArrayList<>(); final ArrayList handList = this.buildHandList(); final long[] boardList = new long[32]; final int size = this.buildBoardList(boardList); for (long[] pair : handList) { for (int i = 0; i < size; ++i) { final long rawBoard = pruningCheck(boardList[i], pair[0], i * 3, depth); if (rawBoard == -1) { continue; } final long nextBoard = updateBoard(rawBoard); if (nextBoard == 0) { return null; } if (pair[1] == 0 || visited.contains(nextBoard)) { continue; } visited.add(nextBoard); next.add(new Zuma(nextBoard, pair[1])); } } return next; } private long pruningCheck(long insBoard, long ball, int pos, int depth) { final long L = (insBoard >> (pos + 3)) & 0x7; final long R = (insBoard >> (pos - 3)) & 0x7; if (depth == 0 && (ball != R) && (L != R) || depth > 0 && (ball != R)) { return -1; } return insBoard | (ball << pos); } private long updateBoard(long board) { long stack = 0; for (int i = 0; i < 64; i += 3) { final long curr = (board >> i) & 0x7; final long top = (stack) & 0x7; ``` ### Python ```python 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 ```