Zuma Game
Hard · Backtracking · String · Dynamic Programming · Stack · Breadth-First Search · Memoization
Problem
A row of colored balls lies on the board, and you hold some balls in your hand. Each color is one of red 'R', yellow 'Y', blue 'B', green 'G' or white 'W'.
On each turn, take any ball from your hand and insert it anywhere in the row, including at either end. Then, while the row contains a group of three or more consecutive balls of the same color, remove that group; removals can chain as the gap closes.
Given the strings board and hand, return the fewest balls you must insert to clear the whole board, or -1 if the balls in your hand cannot do it.
Examples
Input: board = "RRBB", hand = "RB" Output: 2
Insert R next to the reds: RRR disappears, leaving BB. Insert B and the board is empty.
Input: board = "GRRG", hand = "RG" Output: 2
An R removes the reds and closes the gap into GG, which the G then clears.
Input: board = "RRWWRRBBRR", hand = "WB" Output: 2
Split the last pair of reds with the W: RRWWRRBBR(W)R. Now a B between the blues removes BBB, the reds close into RRR and vanish, the whites close into WWW and vanish, and the last reds meet as RRR.
Constraints
- 1 <= len(board) <= 16
- 1 <= len(hand) <= 5
- board and hand use only the characters R, Y, B, G and W
- The starting board has no group of three or more balls of one color
Approaches
- Baseline: breadth-first search over every insertion point — time exponential; far more states than the pruned search, space O(number of states reached)
Follow-up
The "only insert next to a same-colored ball" shortcut that many solutions use is wrong: for board = "RRWWRRBBRR", hand = "WB", every way to clear the board starts by splitting a pair of reds with a ball of another color. That is why the search also tries inserting between two equal balls of another color. With larger hands the state space grows quickly; an A* search with a lower bound (each remaining run of length 1 needs at least 2 balls, of length 2 at least 1) prunes it further.
Related problems
Start free on Cariara · Coding problems · System design studio
