Show problems as
Classic problem #488HardStringDynamic ProgrammingStackBreadth-First SearchMemoization

Zuma Game

Real-world version: Clearing the Rail of Beads
Tracked in this browser only
Read Zuma Game on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rail holds beads, given by rail, and a pouch holds spares, given by pouch. Both are written with the letters R, Y, B, G and W, one letter per bead.

One move takes a bead out of the pouch and pushes it in anywhere on the rail, either end included. Then, over and over for as long as it applies, any run of three or more touching beads of one colour is taken off the rail, which may bring fresh runs together.

The rail starts with no run of three or more beads of one colour.

Return the fewest beads that have to leave the pouch to clear the rail completely, or -1 when no number of moves can clear it.

Examples

Example 1

Input
rail = "RRBBRR", pouch = "B"
Output
1

Pushing the spare between the two middle beads makes three of that colour. Taking those off brings the four outer beads together, and they come off as well, so one bead clears the rail.

Example 2

Input
rail = "WRRW", pouch = "RW"
Output
2

Push the first spare between the two middle beads to make three, which come off and leave the outer pair touching. The second spare then makes three of those.

Example 3

Input
rail = "RY", pouch = "RY"
Output
-1

Each colour appears once on the rail and once in the pouch, so no colour can ever reach three touching beads.

Constraints

  • 1 <= rail.length <= 16
  • 1 <= pouch.length <= 5
  • rail and pouch hold only the letters R, Y, B, G and W
  • the rail starts with no run of three or more beads of one colour

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_min_step(rail: str, pouch: str) -> int:
Java
public int findMinStep(String rail, String pouch)

More on the same topics