Hard
Quiz
#488 Zuma Game
APPROACH
In a Zuma-like game, a single row of colored balls ('R', 'Y', 'B', 'G', 'W') sits on the board. Each turn you may pick one ball from your hand and insert it anywhere in the row. After insertion, any group of 3 or more consecutive same-color balls is removed immediately, and this may trigger further chain removals.
You win by emptying the board. Given the initial board string and the hand string, return the minimum number of insertions needed to clear the board, or -1 if it is impossible.
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.
1 of 4
1:00
What is the optimal approach for this problem?