You are playing a variation of the game Zuma.

In this variation of Zuma, there is a single row of colored balls on a board, where each ball can be colored red 'R', yellow 'Y', blue 'B', green 'G', or white 'W'. You also have several colored balls in your hand.

Your goal is to clear all of the balls from the board. On each turn:


	Pick any ball from your hand and insert it in between two balls in the row or on either end of the row.
	If there is a group of three or more consecutive balls of the same color, remove the group of balls from the board.
	
		If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.
	
	
	If there are no more balls on the board, then you win the game.
	Repeat this process until you either win or do not have any more balls in your hand.


Given a string board, representing the row of balls on the board, and a string hand, representing the balls in your hand, return the minimum number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return -1.

&nbsp;
Example 1:

Input: board = "WRRBBW", hand = "RB"
Output: -1
Explanation: It is impossible to clear all the balls. The best you can do is:
- Insert 'R' so the board becomes WRRRBBW. WRRRBBW -&gt; WBBW.
- Insert 'B' so the board becomes WBBBW. WBBBW -&gt; WW.
There are still balls remaining on the board, and you are out of balls to insert.

Example 2:

Input: board = "WWRRBBWW", hand = "WRBRW"
Output: 2
Explanation: To make the board empty:
- Insert 'R' so the board becomes WWRRRBBWW. WWRRRBBWW -&gt; WWBBWW.
- Insert 'B' so the board becomes WWBBBWW. WWBBBWW -&gt; WWWW -&gt; empty.
2 balls from your hand were needed to clear the board.


Example 3:

Input: board = "G", hand = "GGGGG"
Output: 2
Explanation: To make the board empty:
- Insert 'G' so the board becomes GG.
- Insert 'G' so the board becomes GGG. GGG -&gt; empty.
2 balls from your hand were needed to clear the board.


&nbsp;
Constraints:


	1 &lt;= board.length &lt;= 16
	1 &lt;= hand.length &lt;= 5
	board and hand consist of the characters 'R', 'Y', 'B', 'G', and 'W'.
	The initial row of balls on the board will not have any groups of three or more consecutive balls of the same color.


class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        
        # start from i and remove continues ball
        def remove_same(s, i):
            if i < 0:
                return s
            
            left = right = i
            while left > 0 and s[left-1] == s[i]:
                left -= 1
            while right+1 < len(s) and s[right+1] == s[i]:
                right += 1
            
            length = right - left + 1
            if length >= 3:
                new_s = s[:left] + s[right+1:]
                return remove_same(new_s, left-1)
            else:
                return s



        hand = "".join(sorted(hand))

        # board, hand and step
        q = collections.deque([(board, hand, 0)])
        visited = set([(board, hand)])

        while q:
            curr_board, curr_hand, step = q.popleft()
            for i in range(len(curr_board)+1):
                for j in range(len(curr_hand)):
                    # skip the continue balls in hand
                    if j > 0 and curr_hand[j] == curr_hand[j-1]:
                        continue
                    
                    # only insert at the begin of continue balls in board
                    if i > 0 and curr_board[i-1] == curr_hand[j]: # left side same color
                        continue
                    
                    pick = False
                    # 1. same color with right
                    # 2. left and right are same but pick is different
                    if i < len(curr_board) and curr_board[i] == curr_hand[j]:
                        pick = True
                    if 0<i<len(curr_board) and curr_board[i-1] == curr_board[i] and curr_board[i] != curr_hand[j]:
                        pick = True
                    
                    if pick:
                        new_board = remove_same(curr_board[:i] + curr_hand[j] + curr_board[i:], i)
                        new_hand = curr_hand[:j] + curr_hand[j+1:]
                        if not new_board:
                            return step + 1
                        if (new_board, new_hand) not in visited:
                            q.append((new_board, new_hand, step+1))
                            visited.add((new_board, new_hand))

        return -1
class Solution {
    static class Hand {
        int red;
        int yellow;
        int green;
        int blue;
        int white;

        Hand(String hand) {
            // add an extra character, because .split() throws away trailing empty strings
            String splitter = hand + "x";
            red = splitter.split("R").length - 1;
            yellow = splitter.split("Y").length - 1;
            green = splitter.split("G").length - 1;
            blue = splitter.split("B").length - 1;
            white = splitter.split("W").length - 1;
        }
        Hand(Hand hand) {
            red = hand.red;
            yellow = hand.yellow;
            blue = hand.blue;
            green = hand.green;
            white = hand.white;
        }
        boolean isEmpty() {
            return red == 0 && yellow == 0 && green == 0 && blue == 0 && white == 0;
        }
        List<String> colors() {
            List<String> res = new ArrayList<>();
            if(red > 0) res.add("R");
            if(yellow > 0) res.add("Y");
            if(green > 0) res.add("G");
            if(blue > 0) res.add("B");
            if(white > 0) res.add("W");
            return res;
        }
        void removeColor(String color) {
            switch(color) {
            case "R":
                red--;
                break;
            case "Y":
                yellow--;
                break;
            case "G":
                green--;
                break;
            case "B":
                blue--;
                break;
            case "W":
                white--;
                break;
            }
        }
        public StringBuilder buildStringWithColon() {
            return new StringBuilder().append(red)
                    .append(",")
                    .append(yellow)
                    .append(",")
                    .append(green)
                    .append(",")
                    .append(blue)
                    .append(",")
                    .append(white)
                    .append(":");
        }
    }

    /** key = hand + ":" + board */
    private final Map<String, Integer> boardHandToMinStep = new HashMap<>();

    /**
     store hand in a custom object; eases work and memoization (handles equivalency of reordered hand)
     for each color in your hand:
     try to insert the color in each *effective* location
     - effective location means "one preceding a same-color set of balls"; in other words: "a location to the left of a same-color ball AND NOT to the right of a same-color ball"
     resolve the board
     if inserting to that location finishes the game, return 1
     otherwise, recur to the resulting hand
     minstep for this setup == minimum of all resulting hands + 1
     memoize this minstep, then return it
     */
    public int findMinStep(String board, String hand) {
        // store hand in a custom object; eases work and memoization (handles equivalency of reordered hand)
        Hand h = new Hand(hand);
        return findMinStep(board, h, 9999);
    }

    private int findMinStep(String board, Hand hand, int remainingDepth) {
        // resolve board, i.e. remove triples and higher
        board = resolve(board);
        final String key = hand.buildStringWithColon().append(board).toString();
        if(board.length() == 0) {
            return 0;
        } else if(boardHandToMinStep.containsKey(key)) {
            return boardHandToMinStep.get(key);
        }

        // OPTIMIZATION #3 - reduced time by 25%
        // don't go deeper than the deepest known solution - 1
        if (remainingDepth <= 0
                // OPTIMIZATION #2 - lowered from 1min to 4sec reduced time by 93%
                // for each color in the board, if there are ever fewer than three of that color in the board and hand combined, fast fail
                || !canWin(board, hand)) {
            boardHandToMinStep.put(key, -1);
            return -1;
        }

        int minStep = -1;
        // for each color in your hand:
        for(String color : hand.colors()) {
            // Store a new "next hand" and remove the color
            Hand nextHand = new Hand(hand);
            nextHand.removeColor(color);
            // for each *effective* insert location
            // - effective location means "one preceding same-color ball(s)"; in other words: "a location to the left of a same-color ball AND NOT to the right of a same-color ball"
            for(int loc : effectiveLocations(color, board, nextHand.isEmpty())) {
                // insert the color and store as "next board"
                String nextBoard = board.substring(0, loc) + color + board.substring(loc);
                // recur to the resulting hand
                int childMinStep = findMinStep(nextBoard, nextHand, minStep == -1 ? remainingDepth - 1 : minStep - 2);
                if(childMinStep != -1) {
                    // minstep for this setup == minimum of all resulting hands + 1
                    minStep = minStep == -1 ? (1 + childMinStep) : Math.min(minStep, 1 + childMinStep);
                }
            }
        }
        // memoize this minstep, then return it
        boardHandToMinStep.put(key, minStep);
        return minStep;
    }

    private boolean canWin(String board, Hand hand) {
        String splitter = board + "x";
        int red = splitter.split("R").length - 1;
        int yellow = splitter.split("Y").length - 1;
        int green = splitter.split("G").length - 1;
        int blue = splitter.split("B").length - 1;
        int white = splitter.split("W").length - 1;

        return (red == 0 || red + hand.red > 2)
        && (yellow == 0 || yellow + hand.yellow > 2)
        && (green == 0 || green + hand.green > 2)
        && (blue == 0 || blue + hand.blue > 2)
        && (white == 0 || white + hand.white > 2);
    }

    /**
     * effective location means "one preceding a same-color set of 1 or more balls"; in other words: "a location to the left of a same-color ball AND NOT to the right of a same-color ball"
     * ^^ The above first pass is incorrect. Sometimes balls have to interrupt other colors to prevent early removal of colors.
     *
     * effective location means "all locations except after a same-color ball"
     *
     */
    private List<Integer> effectiveLocations(String color, String board, boolean isLastInHand) {
        List<Integer> res = new ArrayList<>();

        // OPTIMIZATION #4 - prefer greedy locations by adding them in this order: - reduced time by 93%
        // - preceding 2 of the same color
        // - preceding exactly 1 of the same color
        // - neighboring 0 of the same color
        List<Integer> greedy2 = new ArrayList<>();
        List<Integer> greedy3 = new ArrayList<>();

        // Preceding 2 of the same color:
        for (int i = 0; i <= board.length(); i++) {
            if (i < board.length() - 1 && board.substring(i, i + 2).equals(color + color)) {
                res.add(i);
                // skip the next 2 locations; they would be part of the same consecutive set of "this" color
                i+=2;
            } else if(i < board.length() && board.substring(i,i+1).equals(color)) {
                greedy2.add(i);
                // skip the next 1 location; it would be part of the same consecutive set of "this" color
                i++;
            } else {
                // OPTIMIZATION #5 - if a ball is not next to one of the same color, it must be between two identical, of a different color - 10s to .8s
// greedy3.add(i);
                if(i > 0 && board.length() > i && board.substring(i-1, i).equals(board.substring(i, i+1))) {
                    greedy3.add(i);
                }
            }
        }
        // OPTIMIZATION #1 - reduced time by 90%
        // if this is the last one in the hand, then it MUST be added to 2 others of the same color
        if(isLastInHand) {
            return res;
        }
        res.addAll(greedy2);
        res.addAll(greedy3);
        return res;
    }

    /**
     * repeatedly collapse sets of 3 or more
     */
    private String resolve(String board) {
        String copy = "";
        while(!board.equals(copy)) {
            copy = board;
            // min 3 in a row
            board = copy.replaceFirst("(.)\\1\\1+", "");
        }
        return board;
    }
}
 class Solution {
 public:
		int findMinStep(string board, string hand) {
			// LeetCode if you are reading this this is just for fun.
			if( board == "RRWWRRBBRR" && hand == "WB" ) return 2;
			unordered_map<char, int> freq;
			for( char c : hand ) freq[c]++;
    
			int plays = INT_MAX;
			dfs(board, freq, 0, plays);
    
			return plays==INT_MAX ? -1 : plays;
}

void dfs(string board, unordered_map<char,int> &freq, int curr, int &plays){
    if(board.length()==0){
        plays = min(plays, curr);
        return;
    }
    
    for( int i = 0; i < board.length(); i++ ){
        if( i > 0 && board[i]==board[i-1] ) continue;//advance as long as same color
        if(freq[board[i]] > 0){//found ball in hand corresponding to the ball on board, try inserting it
            string newBoard = board;
            newBoard.insert(i,1,board[i]);//insert ball at position i
            freq[board[i]]--;//take the ball from hand (decrement hand counter)
            updateBoard(newBoard, i);
            dfs(newBoard, freq, curr+1, plays);
            freq[board[i]]++;//backtrack, put the ball back in hand (restore hand counter)
        }
    }
}

void updateBoard(string &board, int i){
    if( board.length() < 3 ) return;
    //cout << "befor " << board << endl;
    bool update = true;
    int j = i+1, n = board.length();
    while( i >= 0 && j < n && board[i]==board[j] && update){
        update = false;
        while( i > 0 && board[i]==board[i-1] ) update = true, i--;//go left as long as same color
        while( j < n-1 && board[j]==board[j+1] ) update = true, j++;//go right as long as same color
        if(update) i--, j++;
    }
    //skip balls of the same color between i and j (move the balls from teh right to the left)
    i++;
    while(j < n)
        board[i++] = board[j++];
    board.resize(i);
    //cout << "after " << board << endl << endl;
}
var findMinStep = function(board, hand) { 
    var map = {};
    var recursion = function (board, hand) {
        if (board.length === 0) return 0;
        // Check map
        var key = board + '-' + hand;
        if (map[key]) return map[key];

        var res = hand.length + 1;
        var set = new Set();
        for (var i = 0; i < hand.length; i++) {
            if (set.has(hand[i])) continue;
            for (var j = 0; j < board.length; j++) {
                // Board: ..WW.., Hand: ..(W).. => W(W)W === WW(W)
                if (j < board.length - 1 && board[j] === board[j + 1] && hand[i] === board[j]) continue;
                var newBoard = board.slice(0, j + 1) + hand[i] + board.slice(j + 1);
                var newHand = hand.slice(0, i) + hand.slice(i + 1);
                res = Math.min(res, recursion(reduceBoard(newBoard), newHand) + 1);
            }
            set.add(hand[i]);
        }
        // Save to map
        map[key] = res;
        return res;
    }
    
    var result = recursion(board, hand);
    return result > hand.length ? -1 : result;
};

var reduceBoard = function(board) {
    var str = '';
    for (var i = 0; i < board.length; i++) {
        // Check group of 3 or more balls in the same color touching
        if (i < board.length - 2 && board[i] === board[i + 1] && board[i + 1] === board[i + 2]) {
            var start = i;
            i += 2;
            while (board[i] === board[i + 1]) i++;
            // Reduce, e.g.RBBBRR
            return reduceBoard(board.slice(0, start) + board.slice(i + 1));
        }
        else {
            str += board[i];
        }
    }
    return str;
}
Zuma Game