<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>

class Solution {
    int ans, used;
    unordered_map<char, int> rem;
    stack<pair<char, int>> st;

    // inserted 表示在当前位置与前一个位置同色的情况下，两个位置之间是否插入过异色球
    void dfs(int pos, string &board, bool inserted) {
        if (used >= ans)
            return;

        if (pos == board.size()) {
            if (st.empty())
                ans = used;
            return;
        }

        // 将pos位置的小球加入
        if (!st.empty() && st.top().first == board[pos]) {
            st.top().second++;
        } else {
            st.emplace(board[pos], 1);
        }

        // 1. 不额外插入小球的情形
        // 1.1 当前颜色满三个，且后面没有相同颜色的球
        if (st.top().second >= 3 && (pos + 1 == board.size() || board[pos + 1] != board[pos])) {
            auto tmp = st.top();
            st.pop();
            dfs(pos + 1, board, false);
            st.push(tmp);
        }

        // 1.2. 当前颜色小球不满三个
        // 1.3. 当前颜色小球恰好三个，但当前小球和上一小球不同色，或者之前插入过非同色球，这说明初始情形为XX...X，之后中间的小球被消去，从而形成了XXX，这种情况是允许的。因为我们可改变消去的顺序。如果当前小球和上一小球同色，则说明初始情形为X...XX，此时假设右边还有X，则中间的XX要么结合左边的X，要么结合右边的X，不可能同时结合。如果当前小球数量已经达到四个，则不可能再积累更多同色球，因为最多只可能形成四连珠，五连珠在形成前至少有一边已经达到三个，是不可能形成的。
        if (st.top().second < 3 ||
            (st.top().second == 3 && (board[pos] != board[pos - 1] || inserted)))
            dfs(pos + 1, board, false);

        // 2. 插入与当前位置同色的小球
        if (rem[board[pos]] >= 1 &&
            (pos + 1 == board.size() || board[pos + 1] != board[pos])) {
            int lim = rem[board[pos]];
            for (int i = 1; i <= min(2, lim); ++i) { // 至多插入两个
                // 加入i个同色小球
                rem[board[pos]] -= i;
                used += i;
                st.top().second += i;
                if (st.top().second >= 3) { // 累积同色球达到三个
                    auto tmp = st.top();      // 维护现场
                    st.pop();                 // 消去同色球
                    dfs(pos + 1, board, false);
                    st.push(tmp); // 还原现场
                } else {
                    dfs(pos + 1, board, false);
                }

                // 还原现场
                st.top().second -= i;
                used -= i;
                rem[board[pos]] += i;
            }
        }

        // 3. 当后面有相同颜色的球时，尝试插入与当前位置不同色的小球
        if (pos + 1 < board.size() && board[pos + 1] == board[pos]) {
            auto tmp = st.top(); // 维护现场
            if (tmp.second >= 3) // 消去当前积累的同色小球
                st.pop();

            for (auto[ch, num]: rem) {
                if (ch == board[pos] || num == 0)
                    continue;
                int hi = (tmp.second >= 3) ? min(3, num) : 1; // 如果当前小球积累不足三个，则至多只插入一个分隔
                for (int j = 1; j <= min(3, num); ++j) {
                    rem[ch] -= j;
                    used += j;

                    // 加入j个小球
                    if (!st.empty() && st.top().first == ch) {
                        st.top().second += j;
                    } else {
                        st.emplace(ch, j);
                    }

                    if (st.top().second >= 3) { // 插入的异色球和之前的球累加达到了三个
                        auto tmp2 = st.top(); // 维护现场
                        st.pop();             // 消去同色球
                        dfs(pos + 1, board, true);
                        st.push(tmp2); // 还原现场
                    } else {
                        dfs(pos + 1, board, true);
                    }

                    // 还原现场
                    if (st.top().second > j) {
                        st.top().second -= j;
                    } else {
                        st.pop();
                    }
                    used -= j;
                    rem[ch] += j;
                }
            }

            if (tmp.second >= 3)
                st.push(tmp); // 还原现场
        }

        // 还原现场
        if (st.top().second == 1) {
            st.pop();
        } else {
            st.top().second--;
        }
    }

public:
    int findMinStep(string board, string hand) {
        for (char ch: hand)
            rem[ch]++;

        ans = 1e9;
        used = 0;
        dfs(0, board, false);
        return ans == 1e9 ? -1 : ans;
    }
};

/* DFS: backtracking */
// Both answers are wrong, because we here try to place balls that exist, the following test case can not be solved:
// RRWWRRBBRR -> RRWWRRBBR[W]R -> RRWWRRBB[B]RWR -> RRWWRRRWR -> RRWWWR -> RRR -> empty
// If we try to accomodate this case, TLE
// class Solution {
//     int result;
// public:
//     int findMinStep(string board, string hand) 
//     {
//         result = INT_MAX;
//         unordered_map<char,int>Hand;
//         for (auto x:hand) Hand[x]++;
        
//         DFS(board,Hand,0);
//         if (result==INT_MAX) return -1;
//         else return result;
//     }
    
//     void DFS(string board, unordered_map<char,int>&Hand, int curCount)
//     {
        
//         if (board=="")
//         {
//             result = min(result,curCount);
//             return;
//         }
//         if (curCount>=result) return;
            
//         // Iterate through each ball in hand and iterate each location
//         for (auto elem: Hand)
//         {
            
//             if (elem.second==0) continue;
//             char c = elem.first;
            
//             Hand[c]--;
                        
//             for (int i=0; i<board.size(); i++)
//             {
//                 // if (board[i]!=c) continue;
//                 if (i>0 && board[i]==board[i-1] && board[i] == c) continue;
                
//                 string newBoard = board;
//                 newBoard.insert(i,1,c);
                
//                 newBoard = clean(newBoard);
//                 DFS(newBoard, Hand, curCount+1);
//             }
            
//             Hand[c]++;
            
//         }
//     }
    
//     string clean(string s)
//     {
//         string t="";
//         while (1)
//         {
//             t = "";
//             for (int i=0; i<s.size(); i++)
//             {
//                 int i0=i;
//                 while (i<s.size() && s[i]==s[i0]) i++;
//                 if (i-i0<3)
//                     t = t+s.substr(i0,i-i0);
//                 i--;
//             }
//             if (t==s) return t;
//             s = t;
//         }
        
//         return s;
//     }
// };

/* DFS: backtracking
Iterate the board instead of balls
*/
// class Solution {
// public:
//     int findMinStep(string board, string hand) {
//         res = INT_MAX;
//         unordered_map<char, int> mp;
//         // Calculate the number of balls in hands
//         for(auto const &b : hand){
//             mp[b]++;
//         }

//         // Depth search first each location on the board
//         dfs(board, mp, 0);
//         return res == INT_MAX? -1 : res;
//     }
// private:
//     int res;
//     void dfs(string &board, unordered_map<char, int>&mp, int cur){
//         // Stop condition
//         if(board == ""){
//             res = min(res, cur);
//         }

//         // Early stopping
//         if(cur >= res) return;

//         // Iterate through each location on board and backtrack
//         for(int i = 0; i < board.size(); ++i){
//             // Count current length of the character
//             int idx = i;
//             char c = board[idx];
//             while(idx < board.size() && board[i] == c) ++i;         // This will at least advance one step
//             int len = i - idx;
//             // Try to place and erase elements
//             if(3 - len > 0 && 3 - len <= mp[c]){
//                 board.erase(idx, len);
//                 string newBoard = clean(board);
//                 mp[c] -= (3 - len);
//                 dfs(newBoard, mp, cur + 3 - len);
//                 mp[c] += (3 - len);
//                 board.insert(idx, len, c);
//             }
//             --i;            // Offset that at least one step to find duplicate
//         }

//         return;
//     }

//     // Handle removing adjacent board numbers after a insertion
//     string clean(string s)
//     {
//         string t="";
//         while (1)
//         {
//             t = "";
//             // Construct less than 3-consecutive element string
//             for (int i=0; i<s.size(); i++)
//             {
//                 int idx=i;
//                 while (i<s.size() && s[i]==s[idx]) i++;
//                 int len = i - idx;
//                 if (len < 3)
//                     t = t + s.substr(idx,len);
//                 i--;
//             }
//             // Recursive construct, or early termination
//             if (t == s) return t;
//             s = t;
//         }
//         return s;
//     }
// };
11200