Zuma Game — Hard Problem & Solution

Problem statement

A row of coloured balls lies on the board; each ball is red 'R', yellow 'Y', blue 'B', green 'G' or white 'W'. You also hold some balls in your hand.

In one turn you take any ball from your hand and insert it anywhere in the row — between two balls or at either end. Then, while the row contains a group of three or more consecutive balls of the same colour, that group is removed (removing one group can make its neighbours touch and form a new group, which is removed too).

Return the minimum number of balls you must insert to clear the whole board, or -1 if the balls in your hand are not enough. The starting row never contains three or more consecutive balls of one colour.

Example 1

Input: board = "WRRBBW", hand = "RB"
Output: -1
Explanation: Inserting R then B leaves `WW`, and there is nothing left to finish it.

Example 2

Input: board = "WWRRBBWW", hand = "WRBRW"
Output: 2
Explanation: `WWRR[R]BBWW` clears the reds, then `WWBB[B]WW` clears the blues and the whites merge into four.

Example 3

Input: board = "G", hand = "GGGGG"
Output: 2

Constraints

• 1 <= board.length <= 16
• 1 <= hand.length <= 5
• board and hand consist of the characters 'R', 'Y', 'B', 'G' and 'W'
• The initial board has no group of three or more consecutive balls of the same colour

How to solve Zuma Game

Breadth-first search over game states (row, sorted hand), so the first time the row becomes empty we have used the fewest balls. Pruning the insertion points to the two useful kinds keeps the branching small.

Approach

1. Sort hand; push (board, hand) into the queue and the visited set.
2. Process the queue level by level (level = balls used). For each state, for each insertion index i and each distinct colour c in the hand:
3. skip if the ball before i is already c; keep it only if board[i] == c, or if board[i - 1] == board[i] != c (splitting a pair).
4. Insert, run clean; if the row is empty, return the current level. Otherwise, if (row, hand minus c) is new, enqueue it.
5. If the queue empties, return -1.

Why it works

Breadth-first order guarantees minimality. The pruning is safe: putting c next to a same-coloured ball can always be done at the left end of that group (identical results), and putting c between two different-coloured neighbours, neither equal to c nor equal to each other, never creates or destroys anything that a later, better-placed insertion could not achieve — while splitting an equal pair can matter (it can let the two halves merge with other balls later), so that case is kept.

Complexity

• Time — Exponential in the hand size (≤ 5) — small in practice with the visited set
• Space — O(number of distinct states)

Pitfalls

• Only inserting next to same-coloured balls is not enough: RRWWRRBBRR with hand WB needs a W between the last two Rs.
• After a removal the neighbours may form a new group of 3+; keep cleaning until nothing changes.
• Two identical balls in the hand lead to identical states — try each colour once per position.

Reference solution

Python

def findMinStep(board: str, hand: str) -> int:
    def clean(s):
        while True:
            changed = False
            i = 0
            while i < len(s):
                j = i
                while j < len(s) and s[j] == s[i]:
                    j += 1
                if j - i >= 3:
                    s = s[:i] + s[j:]
                    changed = True
                    break
                i = j
            if not changed:
                return s

    start = ''.join(sorted(hand))
    level = [(board, start)]
    seen = {board + '#' + start}
    step = 0
    while level:
        step += 1
        nxt = []
        for b, h in level:
            for i in range(len(b) + 1):
                for j in range(len(h)):
                    c = h[j]
                    if j > 0 and c == h[j - 1]:
                        continue
                    if i > 0 and b[i - 1] == c:
                        continue
                    worth = (i < len(b) and b[i] == c) or (0 < i < len(b) and b[i - 1] == b[i] and b[i] != c)
                    if not worth:
                        continue
                    nb = clean(b[:i] + c + b[i:])
                    if not nb:
                        return step
                    nh = h[:j] + h[j + 1:]
                    key = nb + '#' + nh
                    if key not in seen:
                        seen.add(key)
                        nxt.append((nb, nh))
        level = nxt
    return -1

JavaScript

var findMinStep = function(board, hand) {
    var clean = function(s) {
        for (;;) {
            var changed = false;
            var i = 0;
            while (i < s.length) {
                var j = i;
                while (j < s.length && s.charAt(j) === s.charAt(i)) j++;
                if (j - i >= 3) {
                    s = s.substring(0, i) + s.substring(j);
                    changed = true;
                    break;
                }
                i = j;
            }
            if (!changed) return s;
        }
    };
    var start = hand.split('').sort().join('');
    var level = [[board, start]];
    var seen = new Set([board + '#' + start]);
    var step = 0;
    while (level.length) {
        step++;
        var nxt = [];
        for (var q = 0; q < level.length; q++) {
            var b = level[q][0], h = level[q][1];
            for (var i = 0; i <= b.length; i++) {
                for (var j = 0; j < h.length; j++) {
                    var c = h.charAt(j);
                    if (j > 0 && c === h.charAt(j - 1)) continue;
                    if (i > 0 && b.charAt(i - 1) === c) continue;
                    var worth = (i < b.length && b.charAt(i) === c) ||
                        (i > 0 && i < b.length && b.charAt(i - 1) === b.charAt(i) && b.charAt(i) !== c);
                    if (!worth) continue;
                    var nb = clean(b.substring(0, i) + c + b.substring(i));
                    if (nb.length === 0) return step;
                    var nh = h.substring(0, j) + h.substring(j + 1);
                    var key = nb + '#' + nh;
                    if (!seen.has(key)) {
                        seen.add(key);
                        nxt.push([nb, nh]);
                    }
                }
            }
        }
        level = nxt;
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Stickers to Spell Word Hard
• Verbal Arithmetic Puzzle Hard
• Expression Add Operators Hard
• Word Search II Hard
• Similar String Groups Hard
• Longest Path With Different Adjacent Characters Hard