> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Zuma Game Python Solution with Tests

> Tested Python solution for LeetCode 488 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 488, [Hard](/catalog/hard). Topics: [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming), [Stack](/catalog/topics/stack), [Breadth-First Search](/catalog/topics/breadth-first-search), [Memoization](/catalog/topics/memoization). [View on LeetCode](https://leetcode.com/problems/zuma-game/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 488   # by problem number
lcpy gen -s zuma_game   # by problem name
```

## Problem

You are playing a variation of the game Zuma.

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 *the **minimum** 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`.

### Examples

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

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

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

### Constraints

* 1 \<= board.length \<= 16
* 1 \<= hand.length \<= 5
* board and hand consist of the characters 'R', 'Y', 'B', 'G', and 'W'.
* The initial row of balls on the board will not have any groups of three or more consecutive balls of the same color.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/zuma_game/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/zuma_game/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
_UNREACHABLE = 10**9


def _clean(row: str) -> str:
    while True:
        kept: list[str] = []
        i = 0
        while i < len(row):
            j = i
            while j < len(row) and row[j] == row[i]:
                j += 1
            if j - i < 3:
                kept.append(row[i:j])
            i = j
        nxt = "".join(kept)
        if nxt == row:
            return row
        row = nxt


def _adjacent(row: str, pos: int, ball: str) -> bool:
    return (pos > 0 and row[pos - 1] == ball) or (pos < len(row) and row[pos] == ball)


class Solution:
    # Time: O((n + h)^h * n * h) states over memoized rows, n <= 21, h <= 5
    # Space: O(states) memo plus recursion depth h
    def find_min_step(self, board: str, hand: str) -> int:
        memo: dict[tuple[str, str], int] = {}

        def search(row: str, balls: str) -> int:
            if not row:
                return 0
            if (row, balls) in memo:
                return memo[(row, balls)]
            if not balls:
                return _UNREACHABLE
            best = _UNREACHABLE
            for i, ball in enumerate(balls):
                if i > 0 and balls[i - 1] == ball:
                    continue
                rest = balls[:i] + balls[i + 1 :]
                for pos in range(len(row) + 1):
                    if not _adjacent(row, pos, ball):
                        continue
                    nxt = _clean(row[:pos] + ball + row[pos:])
                    best = min(best, 1 + search(nxt, rest))
            memo[(row, balls)] = best
            return best

        result = search(board, "".join(sorted(hand)))
        return -1 if result >= _UNREACHABLE else result
```

## Complexity

| Time | Space |
| - | - |
| O((n + h)^h \* n \* h) states over memoized rows, n \<= 21, h \<= 5 | O(states) memo plus recursion depth h |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.