1194. Zuma Game

You have a row of colored balls (board) and balls in your hand. Each turn you insert one hand ball anywhere in the row; whenever three or more of the same color become adjacent they are removed, repeatedly. Return the minimum number of balls you must insert to clear the board, or -1 if it cannot be cleared. The input is JSON {board, hand}.

Input: JSON {board, hand}.

Output: Integer — the minimum insertions, or -1.

Examples

Input: {"board":"WWRRBBWW","hand":"WRBRW"}
Output: 2
Explanation: Two insertions clear the board.

Input: {"board":"WRRBBW","hand":"RB"}
Output: -1
Explanation: Cannot clear.

Input: {"board":"G","hand":"GGGGG"}
Output: 2
Explanation: Insert two greens.

Constraints

• 1<=|board|<=16
• 1<=|hand|<=5

Asked by