Leetcode 488 Solution

class Solution {
    int res;
    int balls[5];

public:
    int get_ball(char ch)
    {
        if (ch == 'R')
            return 0;
        else if (ch == 'Y')
            return 1;
        else if (ch == 'B')
            return 2;
        else if (ch == 'G')
            return 3;
        else if (ch == 'W')
            return 4;
        return 10000;
    }

    void findMinStep(string board, int step)
    {
        stack<pair<char, int>> s;
        for (int i = 0; i < board.size(); i++)
        {
            if (s.empty())
                s.push(make_pair(board[i], 1));
            else
            {
                if (board[i] != s.top().first && s.top().second >= 3)
                    s.pop();

                if (s.empty() || board[i] != s.top().first)
                    s.push(make_pair(board[i], 1));
                else
                    s.top().second++;
            }
        }

        while (s.empty() == false && s.top().second >= 3)
            s.pop();

        if (s.empty())
        {
            if (res == -1 || res > step)
                res = step;
            return;
        }

        string newboard;
        while (s.empty() == false)
        {
            newboard += string(s.top().second, s.top().first);
            s.pop();
        }
        reverse(newboard.begin(), newboard.end());

        for (int i = 0; i < newboard.size(); i++)
        {
            if (i + 1 < newboard.size() && newboard[i] == newboard[i + 1])
                continue;

            auto ball = get_ball(newboard[i]);
            if (balls[ball] > 0)
            {
                balls[ball]--;
                findMinStep(newboard.substr(0, i + 1) + newboard[i] + newboard.substr(i + 1), step + 1);
                balls[ball]++;
            }
        }
    }

    int findMinStep(string board, string hand) {
        res = -1;
        balls[0] = 0;
        balls[1] = 0;
        balls[2] = 0;
        balls[3] = 0;
        balls[4] = 0;

        for (auto ball : hand)
            balls[get_ball(ball)]++;

        findMinStep(board, 0);

        return res;
    }
};