<p>You are playing a variation of the game Zuma.</p>

<p>In this variation of Zuma, there is a <strong>single row</strong> of colored balls on a board, where each ball can be colored red <code>&#39;R&#39;</code>, yellow <code>&#39;Y&#39;</code>, blue <code>&#39;B&#39;</code>, green <code>&#39;G&#39;</code>, or white <code>&#39;W&#39;</code>. You also have several colored balls in your hand.</p>

<p>Your goal is to <strong>clear all</strong> of the balls from the board. On each turn:</p>

<ul>
	<li>Pick <strong>any</strong> ball from your hand and insert it in between two balls in the row or on either end of the row.</li>
	<li>If there is a group of <strong>three or more consecutive balls</strong> of the <strong>same color</strong>, remove the group of balls from the board.
	<ul>
		<li>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.</li>
	</ul>
	</li>
	<li>If there are no more balls on the board, then you win the game.</li>
	<li>Repeat this process until you either win or do not have any more balls in your hand.</li>
</ul>

<p>Given a string <code>board</code>, representing the row of balls on the board, and a string <code>hand</code>, representing the balls in your hand, return <em>the <strong>minimum</strong> 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 </em><code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> board = &quot;WRRBBW&quot;, hand = &quot;RB&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> It is impossible to clear all the balls. The best you can do is:
- Insert &#39;R&#39; so the board becomes WRR<u>R</u>BBW. W<u>RRR</u>BBW -&gt; WBBW.
- Insert &#39;B&#39; so the board becomes WBB<u>B</u>W. W<u>BBB</u>W -&gt; WW.
There are still balls remaining on the board, and you are out of balls to insert.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> board = &quot;WWRRBBWW&quot;, hand = &quot;WRBRW&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make the board empty:
- Insert &#39;R&#39; so the board becomes WWRR<u>R</u>BBWW. WW<u>RRR</u>BBWW -&gt; WWBBWW.
- Insert &#39;B&#39; so the board becomes WWBB<u>B</u>WW. WW<u>BBB</u>WW -&gt; <u>WWWW</u> -&gt; empty.
2 balls from your hand were needed to clear the board.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> board = &quot;G&quot;, hand = &quot;GGGGG&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make the board empty:
- Insert &#39;G&#39; so the board becomes G<u>G</u>.
- Insert &#39;G&#39; so the board becomes GG<u>G</u>. <u>GGG</u> -&gt; empty.
2 balls from your hand were needed to clear the board.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= board.length &lt;= 16</code></li>
	<li><code>1 &lt;= hand.length &lt;= 5</code></li>
	<li><code>board</code> and <code>hand</code> consist of the characters <code>&#39;R&#39;</code>, <code>&#39;Y&#39;</code>, <code>&#39;B&#39;</code>, <code>&#39;G&#39;</code>, and <code>&#39;W&#39;</code>.</li>
	<li>The initial row of balls on the board will <strong>not</strong> have any groups of three or more consecutive balls of the same color.</li>
</ul>

// struct Node {
//     string board;
//     string hand;
//     int step;
// }

class Solution {
public:
    int findMinStep(string board, string hand) {
        // DFS
        // int ans = dfs(board + "#", hand, {});
        // return ans == INT_MAX ? -1 : ans;

        // BFS
        return bfs(board, hand);
    }

    // Problem with bfs/dfs: states may get too many when we go very deep, especially with a big branching factor
    int bfs(const string& board, const string& hand) {
        string new_board = deDup2(board + "#");
        queue<pair<string, string>> q;
        unordered_set<string> visited;
        q.push({new_board, hand});
        visited.insert(new_board + "#" + hand);
        int steps = -1;  // the first node is the source node, with steps=0
        while (!q.empty()) {
            int sz = q.size();
            steps++;
            while (sz-- > 0) {
                auto [curr_board, curr_hand] = q.front(); q.pop();
                // if (curr_board == "#") return steps;
                for (int i = 0; i < curr_board.length(); i++) {
                    for (int j = 0; j < curr_hand.length(); j++) {
                        if (curr_board[i] == curr_hand[j] && (i == 0 || curr_board[i - 1] != curr_hand[j]) ||
                            curr_board[i] != curr_hand[j] && i > 0 && curr_board[i - 1] == curr_board[i])
                        {
                            string next_board = deDup2(curr_board.substr(0, i) + curr_hand[j] + curr_board.substr(i));
                            string next_hand = curr_hand.substr(0, j) + curr_hand.substr(j + 1);
                            string next_hashKey = next_board + "#" + next_hand;
                            if (next_board == "#") return steps + 1;  // early return
                            if (visited.count(next_hashKey)) continue;
                            q.push({next_board, next_hand});
                            visited.insert(next_hashKey);
                        }
                    }
                }
            }
        }
        return -1;
    }
    
    int dfs(string&& board, const string& hand, unordered_map<string, int>&& memo) {
        const string hashKey = board + "#" + hand;
        if (auto it = memo.find(hashKey); it != memo.end()) {
            return it->second;
        }
        // deDup(board);
        board = deDup2(board);
        if (board == "#") {
            return 0;
        }
        
        // iterate over hs at hand which is candidate balls which can cause ball removal in board
        int min_steps = INT_MAX;
        for (int i = 0; i < board.length(); i++) {
            for (int j = 0; j < hand.length(); j++) {
                // slots worthy of trying
                // 1) the slot before the subarray containing the same chars, and board[i] == hand[j], used to remove the subarray
                // 2) slots between equal chars, and board[i] != hand[j], used to break the subarray
                if (board[i] == hand[j] && (i == 0 || board[i - 1] != board[i]) || 
                    board[i] != hand[j] && i > 0 && board[i - 1] == board[i])
                {
                    string new_board = board.substr(0, i) + hand[j] + board.substr(i);
                    string new_hand = hand.substr(0, j) + hand.substr(j + 1);
                    int steps = dfs(move(new_board), new_hand, move(memo));
                    if (steps != INT_MAX) {
                        min_steps = min(min_steps, steps + 1);
                    }
                }
            }
        }
        return memo[hashKey] = min_steps;
    }

    void deDup(string& board) {
        int start = 0;
        for (int i = 0; i < board.length();) {
            while (i < board.length() && board[i] == board[start]) i++;
            if (i - start >= 3) {
                board.erase(start, i - start);
                i = start;
                while (start > 0 && board[start - 1] == board[i]) start--;
                continue;
            }
            start = i;
        }
    }

    string deDup2(const string& board) {
        int start = 0;
        for (int i = 0; i < board.length(); i++) {
            while (i < board.length() && board[i] == board[start]) i++;
            if (i - start >= 3) {
                return deDup2(board.substr(0, start) + board.substr(i));
            }
            start = i;
        }
        return board;
    }
};
145700