LeetCode 488: Zuma Game

Problem Restatement

We are given a row of colored balls called board and some balls in our hand called hand.

Each ball has one of five colors:

On each move, we choose one ball from hand and insert it anywhere in board.

After insertion, if there are three or more consecutive balls of the same color, that whole group disappears. This can cause a chain reaction: after one group disappears, another group of three or more may form and disappear too.

We need to return the minimum number of inserted balls needed to clear the whole board. If it cannot be done, return -1.

The constraints are small: board.length <= 16 and hand.length <= 5. The initial board has no group of three or more equal consecutive balls.

Input and Output

Function shape:

def findMinStep(board: str, hand: str) -> int:
    ...

Examples

Example 1:

board = "WRRBBW"
hand = "RB"

One possible attempt:

Insert R: WRRBBW -> WRRRBBW -> WBBW
Insert B: WBBW -> WBBBW -> WW

The board still has WW, but no balls remain in hand.

Answer:

-1

Example 2:

board = "WWRRBBWW"
hand = "WRBRW"

A valid solution uses two insertions:

Insert R: WWRRBBWW -> WWRRRBBWW -> WWBBWW
Insert B: WWBBWW -> WWBBBWW -> WWWW -> empty

Answer:

2

Example 3:

board = "G"
hand = "GGGGG"

Insert two G balls:

G -> GG -> GGG -> empty

Answer:

2

First Thought: Try Every Move

At each step, we can choose:

1. Which ball color to insert.
2. Where to insert it.

Then we remove any group of three or more equal balls.

Since hand.length <= 5, this search space is small enough for backtracking.

The main difficulty is not the insertion. The main difficulty is correctly simulating chain removals.

For example:

WWBBBWW

First, BBB disappears:

WWWW

Then WWWW also disappears:

empty

So after every insertion, we need to repeatedly remove groups until no group remains.

Key Insight

Use DFS with memoization.

A game state is fully described by:

current board
remaining hand counts

From one state, try every useful insertion. Recursively solve the smaller state after removals.

The answer for a state is the minimum over all valid next moves.

Because the same state can be reached through different insertion orders, memoization avoids repeated work.

Chain Removal

We need a helper function shrink.

It receives a board string and repeatedly removes any consecutive group with length at least 3.

For example:

shrink("WWBBBWW") == ""

Process:

WWBBBWW
WWWW
empty

A clean implementation scans groups from left to right. If it finds a group of length at least 3, it removes that group and starts again.

Algorithm

Represent the hand as counts:

Counter(hand)

Define:

dfs(board)

as the minimum number of insertions needed to clear board using the current hand counts.

For each group of equal balls in board:

1. Suppose the group color is c.
2. Suppose the group length is length.
3. We need need = 3 - length balls to remove this group.
4. If hand[c] >= need, try using need balls of color c.
5. Remove the group, shrink the merged board, and recurse.
6. Restore the hand count.

Why insert only enough balls to finish an existing group?

Because inserting a ball of color c is useful when it helps create a group of at least three. With the small constraints, this group-based DFS gives a direct and efficient search.

Correctness

The helper shrink removes exactly the groups required by the game rule. It repeatedly deletes any consecutive group of length at least 3, and stops only when no such group remains. Therefore, it matches the chain-reaction behavior.

In dfs(board), the algorithm considers every group currently present on the board. For a group of color c and length length, adding 3 - length balls of color c is the smallest insertion count that can immediately remove that group.

Every successful strategy must eventually cause some group to disappear. Consider the first group that disappears in an optimal strategy. Just before it disappears, enough balls of that same color have been inserted to make its length at least 3. The DFS considers the equivalent move of spending the required balls to eliminate such a group, then applies the same chain removals.

After that removal, the remaining problem has the same form: clear the new board with fewer hand balls. The recursive call returns the optimal cost for that smaller state.

The DFS takes the minimum over all possible group removals, so it finds the minimum number of insertions. Memoization does not change the result; it only reuses the already computed answer for the same board and remaining hand counts.

Thus the algorithm returns the optimal answer, or -1 if no sequence can clear the board.

Complexity

The constraints are small: board.length <= 16 and hand.length <= 5, so DFS with memoization is practical.

Implementation

from collections import Counter
from functools import cache
from math import inf

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        hand_count = Counter(hand)

        def shrink(s: str) -> str:
            changed = True

            while changed:
                changed = False
                i = 0
                parts = []

                while i < len(s):
                    j = i

                    while j < len(s) and s[j] == s[i]:
                        j += 1

                    if j - i >= 3:
                        changed = True
                    else:
                        parts.append(s[i:j])

                    i = j

                s = "".join(parts)

            return s

        @cache
        def dfs(state: str, r: int, y: int, b: int, g: int, w: int) -> int:
            if not state:
                return 0

            counts = {
                "R": r,
                "Y": y,
                "B": b,
                "G": g,
                "W": w,
            }

            best = inf
            i = 0

            while i < len(state):
                j = i

                while j < len(state) and state[j] == state[i]:
                    j += 1

                color = state[i]
                length = j - i
                need = 3 - length

                if counts[color] >= need:
                    counts[color] -= need

                    next_state = shrink(state[:i] + state[j:])

                    cost = dfs(
                        next_state,
                        counts["R"],
                        counts["Y"],
                        counts["B"],
                        counts["G"],
                        counts["W"],
                    )

                    if cost != inf:
                        best = min(best, need + cost)

                    counts[color] += need

                i = j

            return best

        ans = dfs(
            board,
            hand_count["R"],
            hand_count["Y"],
            hand_count["B"],
            hand_count["G"],
            hand_count["W"],
        )

        return -1 if ans == inf else ans

Code Explanation

We count the hand balls:

hand_count = Counter(hand)

The shrink function repeatedly removes groups of length at least three:

if j - i >= 3:
    changed = True
else:
    parts.append(s[i:j])

If a group is removed, changed becomes True, so the loop scans again. This handles chain reactions.

The DFS state includes the board and the remaining count of each color:

def dfs(state: str, r: int, y: int, b: int, g: int, w: int) -> int:

This makes the state cacheable.

If the board is empty, no more insertions are needed:

if not state:
    return 0

For each group, compute how many balls are needed to remove it:

need = 3 - length

Since the initial board has no group of three or more, and shrink removes all such groups, remaining groups have length 1 or 2. So need is either 2 or 1.

If we have enough balls, try that move:

if counts[color] >= need:

Remove the group and shrink the result:

next_state = shrink(state[:i] + state[j:])

Then recurse and minimize the total cost.

Testing

def run_tests():
    s = Solution()

    assert s.findMinStep("WRRBBW", "RB") == -1
    assert s.findMinStep("WWRRBBWW", "WRBRW") == 2
    assert s.findMinStep("G", "GGGGG") == 2
    assert s.findMinStep("RBYYBBRRB", "YRBGB") == 3
    assert s.findMinStep("R", "RR") == 2
    assert s.findMinStep("RR", "R") == 1

    print("all tests passed")

run_tests()

Test meaning: