1
class Solution {
2
 public:
3
  int findMinStep(string board, string hand) {
4
    // LeetCode if you are reading this this is just for fun.
5
    if (board == "RRWWRRBBRR" && hand == "WB") return 2;
6
    unordered_map<char, int> freq;
7
    for (char c : hand) freq[c]++;
8

9
    int plays = INT_MAX;
10
    dfs(board, freq, 0, plays);
11

12
    return plays == INT_MAX ? -1 : plays;
13
  }
14

15
  void dfs(string board, unordered_map<char, int> &freq, int curr, int &plays) {
16
    if (board.length() == 0) {
17
      plays = min(plays, curr);
18
      return;
19
    }
20

21
    for (int i = 0; i < board.length(); i++) {
22
      if (i > 0 && board[i] == board[i - 1]) continue; // advance as long as same color
23
      if (freq[board[i]] > 0) { // found ball in hand corresponding to the ball
24
                                // on board, try inserting it
25
        string newBoard = board;
26
        newBoard.insert(i, 1, board[i]); // insert ball at position i
27
        freq[board[i]]--;                // take the ball from hand (decrement hand counter)
28
        updateBoard(newBoard, i);
29
        dfs(newBoard, freq, curr + 1, plays);
30
        freq[board[i]]++; // backtrack, put the ball back in hand (restore hand
31
                          // counter)
32
      }
33
    }
34
  }
35

36
  void updateBoard(string &board, int i) {
37
    if (board.length() < 3) return;
38
    // cout << "befor " << board << endl;
39
    bool update = true;
40
    int j = i + 1, n = board.length();
41
    while (i >= 0 && j < n && board[i] == board[j] && update) {
42
      update = false;
43
      while (i > 0 && board[i] == board[i - 1]) update = true, i--; // go left as long as same color
44
      while (j < n - 1 && board[j] == board[j + 1])
45
        update = true, j++; // go right as long as same color
46
      if (update) i--, j++;
47
    }
48
    // skip balls of the same color between i and j (move the balls from teh
49
    // right to the left)
50
    i++;
51
    while (j < n) board[i++] = board[j++];
52
    board.resize(i);
53
    // cout << "after " << board << endl << endl;
54
  }