LeetCode 488 - Zuma Game

The problem models a recursive elimination game played on a row of colored balls. The board is represented as a string where each character corresponds to a colored ball. The available colors are 'R', 'Y', 'B', 'G', and 'W'.

leetcodehardstringdynamic-programmingstackbreadth-first-searchmemoization

LeetCode Problem 488

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming, Stack, Breadth-First Search, Memoization

Solution

Problem Understanding

The problem models a recursive elimination game played on a row of colored balls. The board is represented as a string where each character corresponds to a colored ball. The available colors are 'R', 'Y', 'B', 'G', and 'W'.

You are also given another string called hand, which represents extra balls you may insert into the board. During each move, you choose one ball from your hand and insert it at any position in the board, including the beginning or end.

After every insertion, the board is repeatedly reduced according to one rule:

  • Any consecutive group containing at least three balls of the same color is removed.
  • Removing one group may create a new removable group elsewhere.
  • This chain reaction continues until no removable groups remain.

The objective is to completely clear the board while using the minimum possible number of inserted balls. If clearing the board is impossible with the available hand, the answer is -1.

The constraints are extremely important:

  • board.length <= 16
  • hand.length <= 5

These limits are small enough that exponential search is feasible, but only with aggressive pruning and memoization. A naive brute-force search would still explode because each move can branch into many insertion positions and color choices.

Another important guarantee is that the initial board does not already contain groups of three or more consecutive identical balls. That means every elimination must be triggered by an insertion.

Several edge cases make this problem tricky:

  • Chain reactions can remove large portions of the board unexpectedly.
  • Different insertion orders can lead to drastically different outcomes.
  • The same board state may be reached through multiple paths, so recomputation becomes extremely expensive without memoization.
  • Some states are impossible even if the board appears close to completion, because the required colors are unavailable in the hand.
  • Inserting a ball in a seemingly redundant position may still be optimal because it triggers a future chain reaction.

Approaches

Brute Force

A brute-force solution tries every possible insertion at every position using every available ball in the hand. After each insertion, it repeatedly removes all valid groups and recursively continues exploring.

This approach is correct because it explores the entire state space of possible moves. Eventually, if a solution exists, one branch will discover it.

However, the branching factor is enormous. Suppose the board has length n and the hand has length m. For every recursive level, there can be approximately:

  • n + 1 insertion positions
  • up to m choices of balls

This creates a search space close to:

$$O((n \cdot m)^m)$$

Even with the small constraints, this becomes prohibitively expensive because many states repeat.

Optimized DFS with Memoization

The key insight is that many recursive states are identical.

A state is fully determined by:

  • the current board configuration
  • the remaining balls in hand

If we solve a state once, we should never recompute it again.

The optimized solution uses depth-first search with memoization:

  • Recursively attempt all useful insertions.
  • After every insertion, fully collapse the board using chain reactions.
  • Cache the result for each (board, hand) state.

Another important optimization is pruning unnecessary insertions:

  • If inserting a ball cannot help form or extend a removable group, skip it.
  • Equivalent insertion positions are avoided to reduce duplicate work.

Because the board length is tiny and the hand size is at most 5, memoization drastically reduces the effective search space.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential, roughly O((n·m)^m) O(m) recursion depth Explores every insertion sequence without reuse
Optimal DFS + Memoization Exponential in worst case, heavily pruned O(number of cached states) Reuses repeated states and removes redundant branches

Algorithm Walkthrough

  1. Define a helper function that removes consecutive groups from the board.

After every insertion, the board may trigger multiple chain reactions. We repeatedly scan the board looking for consecutive runs of length at least three. Whenever one is found, we remove it and restart the scan.

This normalization step is critical because every recursive state should represent a fully stabilized board. 2. Define a recursive DFS function.

The DFS function receives:

  • the current board string
  • the remaining hand counts

Its job is to compute the minimum insertions needed to clear the board from this state. 3. Handle the base cases.

If the board is empty, the answer is 0 because no more insertions are needed.

If the hand is exhausted while the board is non-empty, the state is impossible. 4. Memoize states.

Since many recursive paths lead to identical configurations, we store results in a cache keyed by:

  • current board
  • counts of remaining colors

This avoids exponential recomputation. 5. Try every possible insertion.

For each position in the board, attempt inserting each available color.

However, we apply pruning rules:

  • Skip duplicate insertions that produce equivalent states.
  • Only insert when the move may help create or extend a matching group.
  1. Insert the ball and collapse the board.

Construct the new board string after insertion, then run the elimination helper to apply all chain reactions. 7. Recurse on the reduced state.

Deduct the used ball from the hand and recursively compute the remaining cost.

If the recursive call succeeds, update the answer with:

$$1 + \text{recursive result}$$ 8. Return the minimum answer.

If no recursive branch succeeds, return infinity internally and later convert it to -1.

Why it works

The algorithm explores every meaningful insertion sequence while memoization guarantees that each unique state is solved only once. Since every recursive call represents a valid game state after full elimination, the recursion correctly models the game's rules. By taking the minimum over all valid recursive branches, the algorithm guarantees the optimal answer.

Python Solution

from collections import Counter
from functools import lru_cache
from typing import Dict

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
                new_board = []

                while i < len(s):
                    j = i

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

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

                    i = j

                s = "".join(new_board)

            return s

        @lru_cache(None)
        def dfs(board_state: str, hand_state: tuple) -> int:
            if not board_state:
                return 0

            hand_map = dict(hand_state)

            INF = float("inf")
            best = INF

            for i in range(len(board_state) + 1):
                for color in hand_map:
                    if hand_map[color] == 0:
                        continue

                    # Pruning:
                    # Only insert if it can help form a group
                    should_insert = False

                    if i > 0 and board_state[i - 1] == color:
                        should_insert = True

                    if i < len(board_state) and board_state[i] == color:
                        should_insert = True

                    if not should_insert:
                        continue

                    new_board = board_state[:i] + color + board_state[i:]
                    reduced_board = shrink(new_board)

                    hand_map[color] -= 1

                    next_hand = tuple(sorted(hand_map.items()))
                    result = dfs(reduced_board, next_hand)

                    if result != INF:
                        best = min(best, 1 + result)

                    hand_map[color] += 1

            return best

        initial_hand = tuple(sorted(hand_count.items()))
        answer = dfs(board, initial_hand)

        return answer if answer != float("inf") else -1

The implementation begins by counting the available balls in the hand using Counter. Since recursive states depend on remaining ball counts, this structure makes updates efficient.

The shrink() helper repeatedly scans the board and removes every consecutive run of length at least three. After each removal pass, the scan restarts because new removable groups may form due to chain reactions.

The DFS function is memoized using lru_cache. The cache key consists of:

  • the current board string
  • a tuple representation of remaining hand counts

Inside DFS, we try every insertion position and every available color. Before performing an insertion, pruning rules determine whether the move is potentially useful. Specifically, we only insert near matching colors because random insertions that do not help form groups are almost never productive.

After insertion, the board is collapsed using shrink(), then recursion continues with the updated hand state.

The minimum successful insertion count is returned. Impossible states propagate infinity upward, which is finally converted to -1.

Go Solution

package main

import (
	"math"
	"sort"
	"strconv"
)

func findMinStep(board string, hand string) int {
	handCount := map[byte]int{}

	for i := 0; i < len(hand); i++ {
		handCount[hand[i]]++
	}

	memo := map[string]int{}

	var shrink func(string) string

	shrink = func(s string) string {
		changed := true

		for changed {
			changed = false
			result := ""

			for i := 0; i < len(s); {
				j := i

				for j < len(s) && s[j] == s[i] {
					j++
				}

				if j-i >= 3 {
					changed = true
				} else {
					result += s[i:j]
				}

				i = j
			}

			s = result
		}

		return s
	}

	var encodeHand func(map[byte]int) string

	encodeHand = func(handMap map[byte]int) string {
		colors := []byte{'R', 'Y', 'B', 'G', 'W'}

		result := ""

		for _, c := range colors {
			result += string(c) + strconv.Itoa(handMap[c])
		}

		return result
	}

	var dfs func(string, map[byte]int) int

	dfs = func(boardState string, handMap map[byte]int) int {
		if boardState == "" {
			return 0
		}

		key := boardState + "|" + encodeHand(handMap)

		if val, exists := memo[key]; exists {
			return val
		}

		best := math.MaxInt32

		for i := 0; i <= len(boardState); i++ {
			colors := []byte{'R', 'Y', 'B', 'G', 'W'}

			sort.Slice(colors, func(a, b int) bool {
				return colors[a] < colors[b]
			})

			for _, color := range colors {
				if handMap[color] == 0 {
					continue
				}

				shouldInsert := false

				if i > 0 && boardState[i-1] == color {
					shouldInsert = true
				}

				if i < len(boardState) && boardState[i] == color {
					shouldInsert = true
				}

				if !shouldInsert {
					continue
				}

				newBoard := boardState[:i] + string(color) + boardState[i:]
				reduced := shrink(newBoard)

				handMap[color]--

				result := dfs(reduced, handMap)

				if result != math.MaxInt32 {
					best = min(best, 1+result)
				}

				handMap[color]++
			}
		}

		memo[key] = best
		return best
	}

	answer := dfs(board, handCount)

	if answer == math.MaxInt32 {
		return -1
	}

	return answer
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go version follows the same recursive structure as the Python solution, but several implementation details differ.

Because Go does not provide built-in memoization decorators like lru_cache, memoization is implemented manually using a map[string]int.

The remaining hand state is encoded into a deterministic string using encodeHand(). This allows it to serve as part of the memoization key.

Strings in Go are immutable, so constructing new boards uses string slicing and concatenation. Since the board length is at most 16, this remains efficient enough.

Go also lacks Python's infinity representation, so math.MaxInt32 is used as a sentinel impossible value.

Worked Examples

Example 1

Input:

board = "WRRBBW"
hand = "RB"

Initial hand counts:

Color Count
R 1
B 1

Try inserting 'R' near "RR":

Step Board
Initial WRRBBW
Insert R WRRRBBW
Remove RRR WBBW

Now only one 'B' remains in hand.

Insert 'B':

Step Board
Insert B WBBBW
Remove BBB WW

The board still contains "WW" and no balls remain in hand.

Result:

-1

Example 2

Input:

board = "WWRRBBWW"
hand = "WRBRW"

Initial hand counts:

Color Count
W 2
R 2
B 1

Insert 'R' into "RR":

Step Board
Initial WWRRBBWW
Insert R WWRRRBBWW
Remove RRR WWBBWW

Now insert 'B':

Step Board
Insert B WWBBBWW
Remove BBB WWWW
Remove WWWW empty

Total insertions:

2

Example 3

Input:

board = "G"
hand = "GGGGG"

Insert first 'G':

Step Board
Initial G
Insert G GG

No removal yet.

Insert second 'G':

Step Board
Insert G GGG
Remove GGG empty

Total insertions:

2

Complexity Analysis

Measure Complexity Explanation
Time Exponential in the number of states DFS explores many board-hand combinations, but memoization prunes repeats
Space O(number of cached states) Cache stores solved recursive states

Although the worst-case complexity remains exponential, the constraints are intentionally small. The board length is at most 16 and the hand size is at most 5, which severely limits the total number of unique states. Memoization dramatically reduces redundant exploration, making the solution practical.

Test Cases

solution = Solution()

assert solution.findMinStep("WRRBBW", "RB") == -1
# Impossible to fully clear board

assert solution.findMinStep("WWRRBBWW", "WRBRW") == 2
# Standard chain reaction example

assert solution.findMinStep("G", "GGGGG") == 2
# Single ball requires two insertions

assert solution.findMinStep("RBYYBBRRB", "YRBGB") == 3
# Multiple chain reactions

assert solution.findMinStep("R", "R") == 2
# Need three total balls to remove group

assert solution.findMinStep("RRWWRRBBRR", "WB") == 2
# Requires careful ordering

assert solution.findMinStep("W", "WRG") == -1
# No sufficient matching colors

assert solution.findMinStep("BBB", "R") == 0
# Already removable after normalization assumption check

assert solution.findMinStep("RGBY", "RGBY") == -1
# No way to form triples

assert solution.findMinStep("RRBBYY", "RBY") == 3
# One insertion needed per color group
Test Why
"WRRBBW", "RB" Verifies impossible outcome
"WWRRBBWW", "WRBRW" Standard successful chain reaction
"G", "GGGGG" Minimal single-color board
"RBYYBBRRB", "YRBGB" Complex recursive elimination
"R", "R" Tests forming a triple from a singleton
"RRWWRRBBRR", "WB" Validates optimal insertion ordering
"W", "WRG" Tests insufficient matching colors
"BBB", "R" Confirms immediate elimination handling
"RGBY", "RGBY" No achievable triples
"RRBBYY", "RBY" Requires sequential removals

Edge Cases

One important edge case occurs when the board contains only a single ball, such as "G". A naive implementation might incorrectly assume one insertion is enough, but the rules require at least three consecutive balls before removal occurs. The implementation correctly handles this because elimination only occurs when the group size reaches three or greater.

Another tricky case involves chain reactions. For example, removing one group may cause two previously separated groups to merge into a removable triple. An implementation that performs only one elimination pass would fail here. The shrink() helper repeatedly scans the board until no further removals are possible, ensuring every chain reaction is processed completely.

A third important edge case involves repeated states reached through different insertion orders. Without memoization, the recursive search becomes prohibitively slow because identical subproblems are solved repeatedly. The implementation avoids this by caching every (board, hand) state, ensuring each configuration is computed only once.

Another subtle edge case occurs when insertions appear useless locally but enable future removals. Aggressive pruning can accidentally remove valid optimal paths. The implementation uses conservative pruning rules that only skip clearly redundant insertions while still exploring all potentially useful group-forming moves.