Zuma Game

HardBacktrackingbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a row of colored balls board and a set of balls in your hand hand. Colors are 'R', 'Y', 'B', 'G' and 'W'. On each turn, take any one ball from your hand and insert it anywhere in the row: at either end or between two adjacent balls. Then, if there is a run of **three or more** consecutive balls of the same color, remove it. Removing a run may make two runs touch and form a new run of three or more, which is removed too; keep going until no such run remains. Return the minimum number of balls you must insert to clear the whole board, or -1 if it cannot be cleared with the balls in your hand. The initial board never contains a run of three or more.

Examples

Input: board = "WRRBBW", hand = "RB"
Output: -1
Adding the R gives WRRRBBW -> WBBW, and adding the B then gives WBBBW -> WW. Two W balls remain with nothing left in hand.
Input: board = "WWRRBBWW", hand = "WRBRW"
Output: 2
Insert R to get WWRRRBBWW -> WWBBWW, then insert B to get WWBBBWW -> WWWW -> empty.
Input: board = "G", hand = "GGGGG"
Output: 2
Insert G twice: G -> GG -> GGG -> empty.

Constraints

  • 1 <= board.length <= 16
  • 1 <= hand.length <= 5
  • `board` and `hand` contain only 'R', 'Y', 'B', 'G', 'W'
  • The initial board has no run of three or more same-colored balls

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems