<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 {
private:    
unordered_map<string, int>memo;
public:
    int findMinStep(string board, string hand) {
        int hand_length=hand.length();
        if(hand_length>1){
            for(int i=0; i<hand_length-1; i++){
                int min_idx=i+1;
                char min_char=hand[i+1];
                for(int j=i+1; j<hand_length; j++){
                    
                    if(hand[j]<min_char){
                        min_char=hand[j];
                        min_idx=j;
                    }
                }
                char temp=hand[min_idx];
                hand[min_idx]=hand[i];
                hand[i]=temp;
            }
        }
        return helper(board, hand);
    }
    int helper(string board, string hand){
        if(board.empty()){
            return 0;
        }
        string key=board+"#"+hand;
        if(memo.count(key)){
            return memo[key];
        }
        int res=INT_MAX;
        for(int i=0; i<board.length(); i++){
            for(int j=0; j<hand.length(); j++){
                // cout<<i<<" "<<j<<endl;
                if(j>0&&hand[j]==hand[j-1]){
                    continue;
                }
                bool try_adding=false;
                if(board[i]==hand[j]){
                    try_adding=true;
                }
                else if(i>0&&board[i]==board[i-1]&&board[i]!=hand[j]){
                    try_adding=true;
                }
                if(try_adding){
                    string new_board=board.substr(0,i)+hand[j]+board.substr(i);
                    string updated_board=updating_board(new_board);
                    string new_hand=hand.substr(0, j)+hand.substr(j+1);
                    int step=helper(updated_board, new_hand);
                    if(step!=-1){
                        res=min(res, step+1);
                    }
                }
            }
        }
        if(res==INT_MAX)return memo[key]=-1;
        return memo[key]=res;
    }
    string updating_board(string board){
        int len = board.length();
        int start = 0;

        while (start < len) {
            int end = start;
            while (end < len && board[start] == board[end]) {
                end++;
            }
            if (end - start >= 3) {
                string new_board = board.substr(0, start) + board.substr(end);
                return updating_board(new_board); 
            } else {
                start = end;
            }
        }
        return board;
    }
};

// class Solution {
// public:
// int findMinStep(string board, string hand) {
// 	vector<int> freq(26, 0);
// 	for(char c: hand)
// 		freq[c - 'A']++;
// 	unordered_map<string, int> cache;
// 	return dfs(board, freq, cache);
// }

// int dfs(string board, vector<int>& freq, unordered_map<string, int>& cache) {
//     string key = board + "#" + serialize(freq);
// 	if(cache.count(key)) {
//         return cache[key];
//     }
// 	int r = INT_MAX;
// 	if(board.length() == 0) {            // base case => we have removed all the balls from table
// 		r = 0;
// 	} else {
// 		for(int i = 0; i < board.length(); i++) {     // try inserting a ball from hand at every position on row of balls
// 			for(int j = 0; j < freq.size(); j++) {       // try all the balls at every position
//                 bool worthTrying = true;
//                 if(board[i] - 'A' == j)
//                     worthTrying = true;
//                 else if(0 < i && board[i] == board[i - 1] && board[i] - 'A' != j) 
//                     worthTrying = true;
                    
// 				if(freq[j] > 0 && worthTrying) {      // only if the frequency is more than 0, skipping this line will lead to runtime error
// 					board.insert(board.begin() + i, j + 'A');   // insert ball at ith index
// 					freq[j]--;    // update the frequency of ball

// 					string newStr = updateBoard(board);   // remove groups of 3 or more if possible
// 					int steps = dfs(newStr, freq, cache);   // recursively call the function for the new string board
// 					if(steps != -1) {    // steps will be -1 if we can't remove all the balls using this combination
// 						r = min(r, steps + 1);
// 					}

// 					freq[j]++;  // restore the frequency
// 					board.erase(board.begin() + i);   // remove the ball from this position to try next combination
// 				}
// 			}
// 		}
// 	}
// 	if(r == INT_MAX) r = -1;   // we can't remove all the balls
// 	cache[key] = r;
// 	return r;
// }

// string updateBoard(string board) {
// 	 int start = 0;
// 	 int end = 0; 
// 	 int boardLen = board.length();
// 	 while(start < boardLen) {
// 		 while(end < boardLen && board[start] == board[end]) {
// 			 end++;   // increment end pointer if consecutive balls are of same color
// 		 }
		 
// 		/* here, end will point to the ball next to consecutive balls of same color 
// 		such that  number of balls of same color = end - start */
		
// 		 if(end - start >= 3) {   // remove if 3 or more balls
// 			 string newBoard = board.substr(0, start) + board.substr(end); 
// 			 return updateBoard(newBoard);     // recursively check if there are more groups in the new string
// 		 } else {
// 			 start = end;
// 		 }
// 	 }
// 	 return board;
// }

// string serialize(vector<int>& freq) {
//     string key = "";
//     for(int i = 0; i < freq.size(); i++) {
//         if(freq[i] > 0)
//         key += to_string((char) i + 'A') + to_string(freq[i]);
//     }
//     return key;
// }  
// };

// class Solution {
// private:    
//     unordered_map<string, int> memo;

// public:
//     int findMinStep(string board, string hand) {
//         // Sort the hand string in descending order to make sure we process larger letters first
//         sort(hand.begin(), hand.end(), greater<char>());
//         return helper(board, hand);
//     }

//     int helper(string board, string hand) {
//         if (board.empty()) {
//             return 0;
//         }
        
//         string key = board + "#" + hand;
//         if (memo.count(key)) {
//             return memo[key];
//         }

//         int res = INT_MAX;
//         for (int i = 0; i < board.length(); ++i) {
//             for (int j = 0; j < hand.length(); ++j) {
//                 if (j > 0 && hand[j] == hand[j - 1]) continue;
                
//                 bool try_adding = false;
//                 if (board[i] == hand[j]) {
//                     try_adding = true;
//                 }
//                 if (i > 0 && board[i] == board[i - 1]) {
//                     try_adding = true;
//                 }

//                 if (try_adding) {
//                     string new_board = board.substr(0, i) + hand[j] + board.substr(i);
//                     string updated_board = updateBoard(new_board);
//                     string new_hand = hand.substr(0, j) + hand.substr(j + 1);
//                     int step = helper(updated_board, new_hand);
//                     if (step != INT_MAX) {
//                         res = min(res, step + 1);
//                     }
//                 }
//             }
//         }
//         if (res == INT_MAX) return memo[key] = -1;
//         return memo[key] = res;
//     }

//     string updateBoard(string board) {
//         int len = board.length();
//         int start = 0;

//         while (start < len) {
//             int end = start;
//             while (end < len && board[start] == board[end]) {
//                 end++;
//             }
//             if (end - start >= 3) {
//                 string new_board = board.substr(0, start) + board.substr(end);
//                 return updateBoard(new_board); // Recursively check for more groups
//             } else {
//                 start = end;
//             }
//         }
//         return board;
//     }
// };

191700