1
class Solution {
2
  static class Hand {
3
    int red;
4
    int yellow;
5
    int green;
6
    int blue;
7
    int white;
8

9
    Hand(String hand) {
10
      // add an extra character, because .split() throws away trailing empty strings
11
      String splitter = hand + "x";
12
      red = splitter.split("R").length - 1;
13
      yellow = splitter.split("Y").length - 1;
14
      green = splitter.split("G").length - 1;
15
      blue = splitter.split("B").length - 1;
16
      white = splitter.split("W").length - 1;
17
    }
18

19
    Hand(Hand hand) {
20
      red = hand.red;
21
      yellow = hand.yellow;
22
      blue = hand.blue;
23
      green = hand.green;
24
      white = hand.white;
25
    }
26

27
    boolean isEmpty() {
28
      return red == 0 && yellow == 0 && green == 0 && blue == 0 && white == 0;
29
    }
30

31
    List<String> colors() {
32
      List<String> res = new ArrayList<>();
33
      if (red > 0) res.add("R");
34
      if (yellow > 0) res.add("Y");
35
      if (green > 0) res.add("G");
36
      if (blue > 0) res.add("B");
37
      if (white > 0) res.add("W");
38
      return res;
39
    }
40

41
    void removeColor(String color) {
42
      switch (color) {
43
        case "R":
44
          red--;
45
          break;
46
        case "Y":
47
          yellow--;
48
          break;
49
        case "G":
50
          green--;
51
          break;
52
        case "B":
53
          blue--;
54
          break;
55
        case "W":
56
          white--;
57
          break;
58
      }
59
    }
60

61
    public StringBuilder buildStringWithColon() {
62
      return new StringBuilder()
63
          .append(red)
64
          .append(",")
65
          .append(yellow)
66
          .append(",")
67
          .append(green)
68
          .append(",")
69
          .append(blue)
70
          .append(",")
71
          .append(white)
72
          .append(":");
73
    }
74
  }
75

76
  /** key = hand + ":" + board */
77
  private final Map<String, Integer> boardHandToMinStep = new HashMap<>();
78

79
  /**
80
   * store hand in a custom object; eases work and memoization (handles equivalency of reordered
81
   * hand) for each color in your hand: try to insert the color in each *effective* location -
82
   * effective location means "one preceding a same-color set of balls"; in other words: "a location
83
   * to the left of a same-color ball AND NOT to the right of a same-color ball" resolve the board
84
   * if inserting to that location finishes the game, return 1 otherwise, recur to the resulting
85
   * hand minstep for this setup == minimum of all resulting hands + 1 memoize this minstep, then
86
   * return it
87
   */
88
  public int findMinStep(String board, String hand) {
89
    // store hand in a custom object; eases work and memoization (handles equivalency of reordered
90
    // hand)
91
    Hand h = new Hand(hand);
92
    return findMinStep(board, h, 9999);
93
  }
94

95
  private int findMinStep(String board, Hand hand, int remainingDepth) {
96
    // resolve board, i.e. remove triples and higher
97
    board = resolve(board);
98
    final String key = hand.buildStringWithColon().append(board).toString();
99
    if (board.length() == 0) {
100
      return 0;
101
    } else if (boardHandToMinStep.containsKey(key)) {
102
      return boardHandToMinStep.get(key);
103
    }
104

105
    // OPTIMIZATION #3 - reduced time by 25%
106
    // don't go deeper than the deepest known solution - 1
107
    if (remainingDepth <= 0
108
        // OPTIMIZATION #2 - lowered from 1min to 4sec reduced time by 93%
109
        // for each color in the board, if there are ever fewer than three of that color in the
110
        // board and hand combined, fast fail
111
        || !canWin(board, hand)) {
112
      boardHandToMinStep.put(key, -1);
113
      return -1;
114
    }
115

116
    int minStep = -1;
117
    // for each color in your hand:
118
    for (String color : hand.colors()) {
119
      // Store a new "next hand" and remove the color
120
      Hand nextHand = new Hand(hand);
121
      nextHand.removeColor(color);
122
      // for each *effective* insert location
123
      // - effective location means "one preceding same-color ball(s)"; in other words: "a location
124
      // to the left of a same-color ball AND NOT to the right of a same-color ball"
125
      for (int loc : effectiveLocations(color, board, nextHand.isEmpty())) {
126
        // insert the color and store as "next board"
127
        String nextBoard = board.substring(0, loc) + color + board.substring(loc);
128
        // recur to the resulting hand
129
        int childMinStep =
130
            findMinStep(nextBoard, nextHand, minStep == -1 ? remainingDepth - 1 : minStep - 2);
131
        if (childMinStep != -1) {
132
          // minstep for this setup == minimum of all resulting hands + 1
133
          minStep = minStep == -1 ? (1 + childMinStep) : Math.min(minStep, 1 + childMinStep);
134
        }
135
      }
136
    }
137
    // memoize this minstep, then return it
138
    boardHandToMinStep.put(key, minStep);
139
    return minStep;
140
  }
141

142
  private boolean canWin(String board, Hand hand) {
143
    String splitter = board + "x";
144
    int red = splitter.split("R").length - 1;
145
    int yellow = splitter.split("Y").length - 1;
146
    int green = splitter.split("G").length - 1;
147
    int blue = splitter.split("B").length - 1;
148
    int white = splitter.split("W").length - 1;
149

150
    return (red == 0 || red + hand.red > 2)
151
        && (yellow == 0 || yellow + hand.yellow > 2)
152
        && (green == 0 || green + hand.green > 2)
153
        && (blue == 0 || blue + hand.blue > 2)
154
        && (white == 0 || white + hand.white > 2);
155
  }
156

157
  /**
158
   * effective location means "one preceding a same-color set of 1 or more balls"; in other words:
159
   * "a location to the left of a same-color ball AND NOT to the right of a same-color ball" ^^ The
160
   * above first pass is incorrect. Sometimes balls have to interrupt other colors to prevent early
161
   * removal of colors.
162
   *
163
   * <p>effective location means "all locations except after a same-color ball"
164
   */
165
  private List<Integer> effectiveLocations(String color, String board, boolean isLastInHand) {
166
    List<Integer> res = new ArrayList<>();
167

168
    // OPTIMIZATION #4 - prefer greedy locations by adding them in this order: - reduced time by 93%
169
    // - preceding 2 of the same color
170
    // - preceding exactly 1 of the same color
171
    // - neighboring 0 of the same color
172
    List<Integer> greedy2 = new ArrayList<>();
173
    List<Integer> greedy3 = new ArrayList<>();
174

175
    // Preceding 2 of the same color:
176
    for (int i = 0; i <= board.length(); i++) {
177
      if (i < board.length() - 1 && board.substring(i, i + 2).equals(color + color)) {
178
        res.add(i);
179
        // skip the next 2 locations; they would be part of the same consecutive set of "this" color
180
        i += 2;
181
      } else if (i < board.length() && board.substring(i, i + 1).equals(color)) {
182
        greedy2.add(i);
183
        // skip the next 1 location; it would be part of the same consecutive set of "this" color
184
        i++;
185
      } else {
186
        // OPTIMIZATION #5 - if a ball is not next to one of the same color, it must be between two
187
        // identical, of a different color - 10s to .8s
188
        // greedy3.add(i);
189
        if (i > 0
190
            && board.length() > i
191
            && board.substring(i - 1, i).equals(board.substring(i, i + 1))) {
192
          greedy3.add(i);
193
        }
194
      }
195
    }
196
    // OPTIMIZATION #1 - reduced time by 90%
197
    // if this is the last one in the hand, then it MUST be added to 2 others of the same color
198
    if (isLastInHand) {
199
      return res;
200
    }
201
    res.addAll(greedy2);
202
    res.addAll(greedy3);
203
    return res;
204
  }
205

206
  /** repeatedly collapse sets of 3 or more */
207
  private String resolve(String board) {
208
    String copy = "";
209
    while (!board.equals(copy)) {
210
      copy = board;
211
      // min 3 in a row
212
      board = copy.replaceFirst("(.)\\1\\1+", "");
213
    }
214
    return board;
215
  }
216
}