Zuma Game solution and explanation

import sys

class ZumaGame:
    def find_min_moves(self, board, hand):
        hand_counts = {char: hand.count(char) for char in hand}
        return self.dfs(board + '#', hand_counts)

    def dfs(self, board, hand_counts):
        board = self.remove_consecutives(board)
        if board == '#':
            return 0
        min_steps = sys.maxsize
        n = len(board)
        i = 0

        for j in range(n):
            if board[j] != board[i]:
                need = 3 - (j - i)
                if hand_counts.get(board[i], 0) >= need:
                    hand_counts[board[i]] -= need
                    min_steps = min(min_steps, need + self.dfs(board[:i] + board[j:], hand_counts))
                    hand_counts[board[i]] += need
                i = j

        return min_steps if min_steps != sys.maxsize else -1

    def remove_consecutives(self, board):
        n = len(board)
        stack = []
        for i in range(n):
            if stack and stack[-1][0] == board[i]:
                stack[-1] = (stack[-1][0], stack[-1][1] + 1)
            else:
                stack.append((board[i], 1))

            if stack[-1][1] >= 3:
                stack.pop()

        return ''.join(c * k for c, k in stack)

board = "WRRBBW"
hand = "RB"
game = ZumaGame()
print(game.find_min_moves(board, hand))

#include <iostream>
#include <unordered_map>
#include <string>
#include <climits>

class ZumaGame {
public:
    int findMinMoves(std::string board, std::string hand) {
        std::unordered_map<char, int> handCounts;
        for (char ch : hand) ++handCounts[ch];
        return dfs(board + "#", handCounts);
    }

private:
    std::string removeConsecutives(const std::string& board) {
        int n = board.size();
        std::string result;
        for (int i = 0; i < n; ++i) {
            if (!result.empty() && result.back() == board[i]) {
                if ((++result.back() >= 3)) {
                    result.pop_back();
                }
            } else {
                result.push_back(1);
                result.push_back(board[i]);
            }
        }
        return result;
    }

    int dfs(const std::string& board, std::unordered_map<char, int>& handCounts) {
        std::string reducedBoard = removeConsecutives(board);
        if (reducedBoard == "#") return 0;
        int minSteps = INT_MAX;

        for (int i = 0, j = 0; j <= reducedBoard.size(); ++j) {
            if (j < reducedBoard.size() && reducedBoard[i] == reducedBoard[j]) 
                continue;
            int needed = 3 - (j - i);
            if (handCounts[reducedBoard[i]] >= needed) {
                handCounts[reducedBoard[i]] -= needed;
                int result = dfs(reducedBoard.substr(0, i) + reducedBoard.substr(j), handCounts);
                if (result != -1) minSteps = std::min(minSteps, result + needed);
                handCounts[reducedBoard[i]] += needed;
            }
            i = j;
        }

        return minSteps == INT_MAX ? -1 : minSteps;
    }
};

int main() {
    ZumaGame game;
    std::string board = "WRRBBW";
    std::string hand = "RB";
    std::cout << game.findMinMoves(board, hand) << std::endl;
    return 0;
}

import java.util.HashMap;

class ZumaGame {
    public int findMinStep(String board, String hand) {
        HashMap<Character, Integer> handCounts = new HashMap<>();
        for (char ch : hand.toCharArray()) handCounts.put(ch, handCounts.getOrDefault(ch, 0) + 1);
        return dfs(board + "#", handCounts);
    }

    private int dfs(String board, HashMap<Character, Integer> handCounts) {
        board = shrink(board);
        if ("#".equals(board)) return 0;
        int minSteps = Integer.MAX_VALUE;
        for (int i = 0, j = 0; j <= board.length(); j++) {
            if (j < board.length() && board.charAt(i) == board.charAt(j)) continue;
            int need = 3 - (j - i);
            if (handCounts.getOrDefault(board.charAt(i), 0) >= need) {
                handCounts.put(board.charAt(i), handCounts.get(board.charAt(i)) - need);
                minSteps = Math.min(minSteps, dfs(board.substring(0, i) + board.substring(j), handCounts) + need);
                handCounts.put(board.charAt(i), handCounts.get(board.charAt(i)) + need);
            }
            i = j;
        }
        return minSteps == Integer.MAX_VALUE ? -1 : minSteps;
    }

    private String shrink(String board) {
        int n = board.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(board.charAt(i));
            int len = sb.length();
            if (len >= 3 && sb.charAt(len - 1) == sb.charAt(len - 2) && sb.charAt(len - 2) == sb.charAt(len - 3)) 
                sb.delete(len - 3, len);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        ZumaGame game = new ZumaGame();
        String board = "WRRBBW";
        String hand = "RB";
        System.out.println(game.findMinStep(board, hand));
    }
}

function findMinStep(board, hand) {
    const memo = {};
    const handMap = {};
    for (let char of hand) {
        handMap[char] = (handMap[char] || 0) + 1;
    }

    function dfs(board) {
        if (board === '#') return 0;
        const key = board + '#' + Object.entries(handMap).map(([k, v]) => k + v).join('');
        if (memo[key] !== undefined) return memo[key];

        let i = 0, min_steps = Infinity;
        for (let j = 0; j <= board.length; j++) {
            if (j < board.length && board[j] !== board[i]) continue;
            let need = 3 - (j - i);
            if (handMap[board[i]] >= need) {
                handMap[board[i]] -= need;
                const tempBoard = board.slice(0, i) + board.slice(j);
                const shrinked = shrink(tempBoard);
                min_steps = Math.min(min_steps, dfs(shrinked) + need);
                handMap[board[i]] += need;
            }
            i = j;
        }

        memo[key] = min_steps === Infinity ? -1 : min_steps;
        return memo[key];
    }

    function shrink(b) {
        let result;
        do {
            result = b;
            b = b.replace(/(\w)\1{2,}/g, '');
        } while (b !== result);
        return b;
    }

    return dfs(board + '#');
}

console.log(findMinStep('WRRBBW', 'RB'));