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 _theminimum 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.
Input: board ="WRRBBW", hand ="RB" Output:-1 Explanation: It is impossible to clear all the balls. The best you can dois:- Insert 'R' so the board becomes WRR _R_ BBW. W _RRR_ BBW -> WBBW.- Insert 'B' so the board becomes WBB _B_ W. W _BBB_ W -> WW. There are still balls remaining on the board, and you are out of balls to insert.
Input: board ="WWRRBBWW", hand ="WRBRW" Output:2 Explanation: To make the board empty:- Insert 'R' so the board becomes WWRR _R_ BBWW. WW _RRR_ BBWW -> WWBBWW.- Insert 'B' so the board becomes WWBB _B_ WW. WW _BBB_ WW -> _WWWW_ -> empty.2 balls from your hand were needed to clear the board.
Input: board ="G", hand ="GGGGG" Output:2 Explanation: To make the board empty:- Insert 'G' so the board becomes G _G_.- Insert 'G' so the board becomes GG _G_. _GGG_ -> empty.2 balls from your hand were needed to clear the board.
The key idea is to try every possible way to insert a ball from the hand into the board and recursively clear the board, using memoization to avoid recomputation. We simulate the process, always removing groups of three or more consecutive balls of the same color after each insertion, and keep track of the minimum number of insertions needed.
classSolution {
funfindMinStep(board: String, hand: String): Int {
val cnt = hand.groupingBy { it }.eachCount().toMutableMap()
val memo = mutableMapOf<String, Int>()
funshrink(s: String): String {
var i = 0while (i < s.length) {
var j = i
while (j < s.length && s[j] == s[i]) j++if (j - i >=3) return shrink(s.substring(0, i) + s.substring(j))
i = j
}
return s
}
fundfs(b: String, c: MutableMap<Char, Int>): Int {
val sb = StringBuilder(b)
val key = sb.append("#").apply {
c.forEach { (k, v) -> append(k).append(v) }
}.toString()
if (memo.containsKey(key)) return memo[key]!!val nb = shrink(b)
if (nb.isEmpty()) return0var ans = Int.MAX_VALUE
for (i in0..nb.length) {
for ((k, v) in c) {
if (v ==0) continueif (i > 0&& nb[i-1] == k) continue c[k] = v - 1val res = dfs(nb.substring(0, i) + k + nb.substring(i), c)
if (res !=Int.MAX_VALUE) ans = minOf(ans, 1 + res)
c[k] = v
}
}
memo[key] = ans
return ans
}
val ans = dfs(board, cnt)
returnif (ans ==Int.MAX_VALUE) -1else ans
}
}
classSolution:
deffindMinStep(self, board: str, hand: str) -> int:
from collections import Counter
from functools import lru_cache
cnt = Counter(hand)
defshrink(s: str) -> str:
i =0while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j +=1if j - i >=3:
return shrink(s[:i] + s[j:])
i = j
return s
memo = {}
defdfs(b: str, c: tuple) -> int:
b = shrink(b)
ifnot b:
return0 key = (b, c)
if key in memo:
return memo[key]
ans = float('inf')
c_dict = dict(zip('RYBGW', c))
for i in range(len(b)+1):
for idx, k in enumerate('RYBGW'):
if c_dict[k] ==0:
continueif i >0and b[i-1] == k:
continue c_dict[k] -=1 nc = tuple(c_dict[x] for x in'RYBGW')
res = dfs(b[:i]+k+b[i:], nc)
if res != float('inf'):
ans = min(ans, 1+res)
c_dict[k] +=1 memo[key] = ans
return ans
c_tuple = tuple(cnt.get(x, 0) for x in'RYBGW')
ans = dfs(board, c_tuple)
return-1if ans == float('inf') else ans
⏰ Time complexity: O(2^(n+m) * n^2) — For each state (board, hand), we try all insertions and all hand balls, and the board can shrink recursively. The number of unique states is exponential in board and hand size, but memoization prunes repeated work.
🧺 Space complexity: O(2^(n+m) * n) — For memoization and recursion stack, where n is the board length and m is the hand length.