1379. Zuma Game — Bitmask Interval DP

A row of coloured balls is given as board, and you hold the balls in hand. On each turn you insert one ball from your hand anywhere in the row; whenever three or more balls of the same colour become adjacent they are removed, and this removal repeats until no such group remains. Return the fewest balls you must insert to clear the board entirely, or -1 if it cannot be cleared.

Input: A JSON object {"board": <string of colours>, "hand": <string of colours>} using the letters R, Y, B, G and W.

Output: Return the minimum number of inserted balls, or -1 if clearing is impossible.

Examples

Input: {"board":"WRRBBW","hand":"RB"}
Output: -1
Explanation: The hand cannot clear this row -> -1.

Input: {"board":"WWRRBBWW","hand":"WRBRW"}
Output: 2
Explanation: Two well-placed balls trigger a full cascade.

Constraints

• 1 <= len(board) <= 16
• 1 <= len(hand) <= 5
• colours are R, Y, B, G, W

Asked by