# 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:

| Character | Color |
|---|---|
| `R` | Red |
| `Y` | Yellow |
| `B` | Blue |
| `G` | Green |
| `W` | White |

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

| Item | Meaning |
|---|---|
| Input | `board`, a string of current balls |
| Input | `hand`, a string of available balls |
| Output | Minimum number of insertions needed |
| Impossible case | Return `-1` |
| Colors | `R`, `Y`, `B`, `G`, `W` |

Function shape:

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

## Examples

Example 1:

```python
board = "WRRBBW"
hand = "RB"
```

One possible attempt:

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

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

Answer:

```python
-1
```

Example 2:

```python
board = "WWRRBBWW"
hand = "WRBRW"
```

A valid solution uses two insertions:

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

Answer:

```python
2
```

Example 3:

```python
board = "G"
hand = "GGGGG"
```

Insert two `G` balls:

```text
G -> GG -> GGG -> empty
```

Answer:

```python
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:

```text
WWBBBWW
```

First, `BBB` disappears:

```text
WWWW
```

Then `WWWW` also disappears:

```text
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:

```text
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:

```python
shrink("WWBBBWW") == ""
```

Process:

```text
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:

```python
Counter(hand)
```

Define:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | Exponential in `hand.length` | The game is a bounded search over insertion choices |
| Space | Exponential in `hand.length` | Memoization stores reachable states |

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

## Implementation

```python
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:

```python
hand_count = Counter(hand)
```

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

```python
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:

```python
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:

```python
if not state:
    return 0
```

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

```python
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:

```python
if counts[color] >= need:
```

Remove the group and shrink the result:

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

Then recurse and minimize the total cost.

## Testing

```python
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:

| Test | Why |
|---|---|
| `"WRRBBW", "RB"` | Impossible official example |
| `"WWRRBBWW", "WRBRW"` | Chain reaction official example |
| `"G", "GGGGG"` | Single ball needs two insertions |
| `"RBYYBBRRB", "YRBGB"` | Multi-color hard case |
| `"R", "RR"` | One group of length one |
| `"RR", "R"` | One group of length two |