package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/zuma-game/
 */
public class Problem488 {
    public int findMinStep(String board, String hand) {
        Map<Character, Integer> handMap = new HashMap<>();
        for (char c : hand.toCharArray()) {
            if (!handMap.containsKey(c)) {
                handMap.put(c, 1);
            } else {
                handMap.put(c, handMap.get(c) + 1);
            }
        }
        int result = findMinStep(board + ".", handMap);
        return (result == 6) ? -1 : result;
    }

    private static int findMinStep(String board, Map<Character, Integer> hand) {
        board = remove(board);
        if (board.equals(".")) {
            return 0;
        }
        int min = 6;
        for (int i = 0, j = 0; j < board.length(); j++) {
            if (board.charAt(i) == board.charAt(j)) {
                continue;
            }
            int need = 3 - (j - i);
            if (hand.containsKey(board.charAt(i))) {
                int count = hand.get(board.charAt(i));
                if (count >= need && count - need >= 0) {
                    hand.put(board.charAt(i), count - need);
                    String newBoard = board.substring(0, i) + board.substring(j);
                    min = Math.min(min, need + findMinStep(newBoard, hand));
                    // backtrack
                    hand.put(board.charAt(i), hand.get(board.charAt(i)) + need);
                }
            }
            i = j;
        }
        return  min;
    }

    private static String remove(String board) {
        for (int i = 0, j = 0; j < board.length(); j++) {
            if (board.charAt(j) == board.charAt(i)) {
                continue;
            }
            if (j - i >= 3) {
                return remove(board.substring(0, i) + board.substring(j));
            }
            i = j;
        }
        return board;
    }

    public static void main(String[] args) {
        Problem488 prob = new Problem488();
        System.out.println(prob.findMinStep("WRRBBW", "RB")); // -1
        System.out.println(prob.findMinStep("WWRRBBWW", "WRBRW")); // 2
        System.out.println(prob.findMinStep("G", "GGGGG")); // 2
        System.out.println(prob.findMinStep("RBYYBBRRB", "YRBGB")); // 3
        System.out.println(prob.findMinStep("RRWWRRW", "WR")); // -1
    }
}

@@ -1935,450 +1935,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem488 prob = new Problem488();%0A        System.out.println(prob.findMinStep(%22WRRBBW%22, %22RB%22)); // -1%0A        System.out.println(prob.findMinStep(%22WWRRBBWW%22, %22WRBRW%22)); // 2%0A        System.out.println(prob.findMinStep(%22G%22, %22GGGGG%22)); // 2%0A        System.out.println(prob.findMinStep(%22RBYYBBRRB%22, %22YRBGB%22)); // 3%0A        System.out.println(prob.findMinStep(%22RRWWRRW%22, %22WR%22)); // -1%0A    %7D
 %0A%7D%0A

Solve problem 488