1
var findMinStep = function (board, hand) {
2
  var map = {};
3
  var recursion = function (board, hand) {
4
    if (board.length === 0) return 0;
5
    // Check map
6
    var key = board + "-" + hand;
7
    if (map[key]) return map[key];
8

9
    var res = hand.length + 1;
10
    var set = new Set();
11
    for (var i = 0; i < hand.length; i++) {
12
      if (set.has(hand[i])) continue;
13
      for (var j = 0; j < board.length; j++) {
14
        // Board: ..WW.., Hand: ..(W).. => W(W)W === WW(W)
15
        if (
16
          j < board.length - 1 &&
17
          board[j] === board[j + 1] &&
18
          hand[i] === board[j]
19
        )
20
          continue;
21
        var newBoard = board.slice(0, j + 1) + hand[i] + board.slice(j + 1);
22
        var newHand = hand.slice(0, i) + hand.slice(i + 1);
23
        res = Math.min(res, recursion(reduceBoard(newBoard), newHand) + 1);
24
      }
25
      set.add(hand[i]);
26
    }
27
    // Save to map
28
    map[key] = res;
29
    return res;
30
  };
31

32
  var result = recursion(board, hand);
33
  return result > hand.length ? -1 : result;
34
};
35

36
var reduceBoard = function (board) {
37
  var str = "";
38
  for (var i = 0; i < board.length; i++) {
39
    // Check group of 3 or more balls in the same color touching
40
    if (
41
      i < board.length - 2 &&
42
      board[i] === board[i + 1] &&
43
      board[i + 1] === board[i + 2]
44
    ) {
45
      var start = i;
46
      i += 2;
47
      while (board[i] === board[i + 1]) i++;
48
      // Reduce, e.g.RBBBRR
49
      return reduceBoard(board.slice(0, start) + board.slice(i + 1));
50
    } else {
51
      str += board[i];
52
    }
53
  }
54
  return str;
55
};