The Zuma Game problem presents you with a string board representing a row of colored balls and a string hand representing balls you can insert into the row. Each ball is labeled with a capital letter, such as 'R', 'Y', 'B', 'G', or 'W'. Your goal is to clear the board by inserting as few balls as possible from your hand. When three or more consecutive balls of the same color appear, they are removed from the board, and this process repeats as possible. You can insert any ball from your hand into any position on the board, but each ball from your hand can be used only once. If it is impossible to clear the board, return -1; otherwise, return the minimum number of balls needed.
hand at any position in board.hand can only be used once.-1 if it's not possible.
At first glance, this problem looks like it could be solved by trying all possible insertions of balls from hand into board and checking if the board can be cleared. However, the number of possible insertions grows rapidly as the board and hand get larger, making brute-force approaches infeasible for anything but the smallest inputs.
To solve this efficiently, we need to avoid redundant work. We can do this by:
Let's break down the steps to solve the Zuma Game:
board (string) and the current hand (multiset or counter of balls left).
hand into any position in board.
hand is empty but the board is not, this path fails.
-1 if no path clears the board.
We use a hash map (dictionary) for the hand for O(1) lookups and a string to represent the board for easy manipulation. The recursive function tries all possible insertions, always simulating the removal of balls after each insertion.
Sample Input:
board = "WRRBBW", hand = "RB"
Let's trace the solution step by step:
W R R B B W. Hand has R and B.
R at position 1 (after the first W): W R R R B B W. This creates a group of three R's, so they are removed: W B B W.
B. Try inserting B at position 1 (after W): W B B B W. Three B's are removed: W W.
-1.
Brute-force Approach:
The brute-force method would try every possible insertion for every ball in the hand at every position in the board, leading to exponential time complexity: O((n * m)!), where n is the board length and m is the hand size.
Optimized Approach:
By using memoization, we reduce redundant work by not revisiting the same (board, hand) state. The number of unique states is O(board configurations * hand configurations), but since both are short (board ≤ 20, hand ≤ 5), this is manageable. The overall time complexity is still exponential in the worst case, but practical for the given constraints.
Space complexity is dominated by the memoization table and the recursion stack, both of which are proportional to the number of unique (board, hand) states.
The Zuma Game problem is a challenging state-search problem that is efficiently solved using recursive DFS with memoization. The key insights are to always remove consecutive balls after each insertion, and to use a hash map to remember already-explored states. This avoids redundant work and makes the solution feasible for the problem's constraints. The approach elegantly balances exhaustive search with practical optimizations, making it a great example of using DFS and memoization together.
from collections import Counter
class Solution:
def findMinStep(self, board: str, hand: str) -> int:
memo = {}
def remove_consecutive(s):
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
if j - i >= 3:
return remove_consecutive(s[:i] + s[j:])
i = j
return s
def dfs(b, h):
if not b:
return 0
key = (b, tuple(sorted(h.items())))
if key in memo:
return memo[key]
res = float('inf')
for i in range(len(b)+1):
for c in h:
if h[c] == 0:
continue
# Skip duplicate insertions
if i > 0 and b[i-1] == c:
continue
# Insert c at position i
newb = remove_consecutive(b[:i] + c + b[i:])
h[c] -= 1
temp = dfs(newb, h)
if temp != -1:
res = min(res, temp + 1)
h[c] += 1
memo[key] = -1 if res == float('inf') else res
return memo[key]
hand_counter = Counter(hand)
return dfs(board, hand_counter)
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
unordered_map<string, int> memo;
string removeConsecutive(string s) {
int i = 0;
while (i < s.size()) {
int j = i;
while (j < s.size() && s[j] == s[i]) j++;
if (j - i >= 3)
return removeConsecutive(s.substr(0, i) + s.substr(j));
i = j;
}
return s;
}
int dfs(string board, vector<int>& hand) {
if (board.empty()) return 0;
string key = board + "#" + to_string(hand[0]) + to_string(hand[1]) + to_string(hand[2]) + to_string(hand[3]) + to_string(hand[4]);
if (memo.count(key)) return memo[key];
int res = INT_MAX;
char colors[5] = {'R', 'Y', 'B', 'G', 'W'};
for (int i = 0; i <= board.size(); ++i) {
for (int k = 0; k < 5; ++k) {
if (hand[k] == 0) continue;
if (i > 0 && board[i-1] == colors[k]) continue;
string newb = board.substr(0, i) + colors[k] + board.substr(i);
newb = removeConsecutive(newb);
hand[k]--;
int temp = dfs(newb, hand);
if (temp != -1)
res = min(res, temp + 1);
hand[k]++;
}
}
memo[key] = (res == INT_MAX) ? -1 : res;
return memo[key];
}
int findMinStep(string board, string hand) {
vector<int> handCount(5, 0);
for (char c : hand) {
if (c == 'R') handCount[0]++;
else if (c == 'Y') handCount[1]++;
else if (c == 'B') handCount[2]++;
else if (c == 'G') handCount[3]++;
else if (c == 'W') handCount[4]++;
}
memo.clear();
return dfs(board, handCount);
}
};
import java.util.*;
class Solution {
Map<String, Integer> memo = new HashMap<>();
private String removeConsecutive(String s) {
int i = 0;
while (i < s.length()) {
int j = i;
while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
if (j - i >= 3) {
return removeConsecutive(s.substring(0, i) + s.substring(j));
}
i = j;
}
return s;
}
private int dfs(String board, int[] hand) {
if (board.length() == 0) return 0;
String key = board + Arrays.toString(hand);
if (memo.containsKey(key)) return memo.get(key);
int res = Integer.MAX_VALUE;
char[] colors = {'R', 'Y', 'B', 'G', 'W'};
for (int i = 0; i <= board.length(); ++i) {
for (int k = 0; k < 5; ++k) {
if (hand[k] == 0) continue;
if (i > 0 && board.charAt(i-1) == colors[k]) continue;
String newb = board.substring(0, i) + colors[k] + board.substring(i);
newb = removeConsecutive(newb);
hand[k]--;
int temp = dfs(newb, hand);
if (temp != -1) res = Math.min(res, temp + 1);
hand[k]++;
}
}
memo.put(key, res == Integer.MAX_VALUE ? -1 : res);
return memo.get(key);
}
public int findMinStep(String board, String hand) {
int[] handCount = new int[5];
for (char c : hand.toCharArray()) {
if (c == 'R') handCount[0]++;
else if (c == 'Y') handCount[1]++;
else if (c == 'B') handCount[2]++;
else if (c == 'G') handCount[3]++;
else if (c == 'W') handCount[4]++;
}
memo.clear();
return dfs(board, handCount);
}
}
var findMinStep = function(board, hand) {
const memo = new Map();
function removeConsecutive(s) {
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) j++;
if (j - i >= 3) {
return removeConsecutive(s.slice(0, i) + s.slice(j));
}
i = j;
}
return s;
}
function dfs(b, h) {
if (b.length === 0) return 0;
const key = b + '#' + Object.entries(h).sort().map(([k, v]) => k + v).join('');
if (memo.has(key)) return memo.get(key);
let res = Infinity;
for (let i = 0; i <= b.length; ++i) {
for (const c in h) {
if (h[c] === 0) continue;
if (i > 0 && b[i-1] === c) continue;
let newb = removeConsecutive(b.slice(0, i) + c + b.slice(i));
h[c]--;
let temp = dfs(newb, h);
if (temp !== -1) res = Math.min(res, temp + 1);
h[c]++;
}
}
memo.set(key, res === Infinity ? -1 : res);
return memo.get(key);
}
const handCount = {};
for (let c of hand) handCount[c] = (handCount[c] || 0) + 1;
return dfs(board, handCount);
};