# Leetcode 488 Solution

https://leetcode.com/problems/zuma-game

## 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;
}
};
``````