Zuma Game

Moderate
0/80
Average time to solve is 20m
2 upvotes
Asked in companies
SalesforceAmazon

Problem statement

You have several balls on the table in the form of a string named 'BOARD'. The colors of the balls can be red(R), blue(B), green(G), white(W), and yellow(Y). You also have several balls in your hand in the form of a string named 'hand'. Each time, you can do the following operations:

1. Choose a ball from the string 'HAND', and insert it anywhere on the string 'BOARD'.

2. If there is a group of strictly more than 2 balls of the same color touching each other, remove them from the string 'BOARD'. Keep doing this until the string 'board' becomes empty or no more balls can satisfy this condition.

Your task is to find the minimum number of insertions required to make the 'BOARD' empty. If it is not possible to make the string 'BOARD' empty, then print -1.

Note:

1) Both strings will be non-empty and will only contain the characters ‘R’, ‘B’, ‘G’, ‘W’, and ‘Y’.

2) Initially, the string 'BOARD' won’t have more than 2 balls of the same colors touching each other.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a string 'BOARD', as described in the problem statement.

The second line of each test case contains a string 'HAND', as described in the problem statement.
Output Format: 
For each test case, print a single line containing a single integer denoting the minimum number of insertions required to make the string 'BOARD' empty or -1 if it is impossible to make the 'board' empty.

The output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= |BOARD| <= 10
1 <= |HAND| <= 4

Where ‘T’ denotes the number of test cases.

Time Limit: 1 sec.
Sample Input 1:
1
YYRR
YR
Sample Output 1:
2
Explanation for sample input 1:
One of the possible order of insertions: YYRR -> YY[Y]RR -> RR -> RR[R] -> empty. You required 2 insertions. There is no possible solution with only one insertion.
Sample Input 2:
1
RR
YG
Sample Output 2:
-1
Explanation for sample input 2:
It is not possible to make the string board empty.
Hint

Think of a recursive solution.

Approaches (1)
Recursive Approach

The idea here is to use recursion. At each step, we plan to insert the remaining balls in the string hand to the string board. Now the question arises, in which position do we have to insert the ‘i’th character of the string hand? The answer is simple; we have to insert ‘i’th character to all the positions on board to get all possible answers. That’s why we are using the recursive approach. After inserting ‘i’th character to a particular position, we have to always remove all consecutive balls of the same colors if their count is more than 2. After removing, we have to call the function again with the new board and another string hand character. This process continues until the length of the string board will become zero. So, if the board becomes empty, then we return the count of the insertions. Or, if all the balls in hand are inserted, and we haven’t found a solution, then also return. But in this case, we have to return a big integer as we are finding the minimum of all the total insertions, and this case doesn’t end up with a possible solution. After returning, we have to insert ‘i’th character to the next position and again call the same function and follow the exact process.

 

Again a question arises that what will be the order we have to follow in the string hand? Is any random order leads us to a possible solution? Or is there any particular order available? Well, a one-word answer is to think greedily! First, find the count of each color ball on the string board. Now, sort the string hand according to these counts. The minimum count colors ball will come first, and the maximum count colors ball will come last. This is one of the orders which we have to follow. Another order is to reverse the string hand and call the recursive function. The output must be the minimum of the recursive function’s return value with the above two orders.

 

Steps:

  • Create a vector of pair of data type int, char named count of size 26 to store the count of each character of the string board, vector<pair<int, char>> count(26).
  • Run a loop to initialize each first element of the pair to 0 and second to char of the vector count, so in each iteration:
    • Set count[i].first = 0, count[i].second = i+’A’.
  • Run a loop from i = 0 to the size of the string board, in each iteration:
    • count[board[i]-’A’].first++.
  • Create a HashMap named frequency for string the count of each character of the string hand.
  • Run a loop from i = 0 to the size of the string hand, in each iteration:
    • frequency[hand[i]]++.
  • Sort the vector of pair count.
  • Make the string hand empty, as we are making it as new according to the string board’s characters’ count.
  • Run a loop from i = 0  to i < 26, in each iteration:
    • Run a loop from j = 0 to j < frequency[count[i].second], in each iteration:
      • hand += count[i].second.
  • After completing these steps, we get our new string hand which is sorted according to the count as discussed earlier.
  • Call the function isEmpty(index, board, inserted, hand), where index is the current index of the string hand that is initially 0, board is the given string, inserted is the count of characters that have been inserted that is initially 0, and hand is the string already described.
  • Now, reverse the string hand as this is the 2nd order in which we have to call the function isEmpty again.
  • Finally, return the minimum of the above two functions calling.

 

int isEmpty(int ind, string &board, int inserted, string &hand):

  • If the length of the string board becomes 0, then return the number inserted, as we have found a possible solution.
  • If index == hand.length(), then return some big integer, and in our case, we can return 100 also, as we have not found a solution and the string hand becomes empty.
  • Now, call the function again without insertion, i.e., isEmpty(ind+1, board, inserted, hand), and create a variable named res to store the return value of this step.
  • Declare a variable i = 0.
  • Run a while loop until i becomes greater than board.size(), in each iteration:
    • Insert the character hand[ind] at the ith position of the string board, and make a new string named newBoard, newBoard = board[:i] + hand[ind] + board[i:].
    • Call another function named remove(newBoard), which is removing consecutive occurrence of the balls of the same colors with a count greater than 2.
    • The above function returning an updated string which we can store in our string newBoard.
    • Call the function isEmpty(index+1, newBoard, inserted+1, hand) and also update the res with the return value if previously it is greater than the return value of this function.
    • Just increment i, because we have to now insert hand[index] to the next position.
  • Finally, return res.

 

string remove(string &board):

  • This function is just removing all consecutive balls of the same colors if their count is more than 2.
  • Run a loop with variable i = 1, j = 0 to i < board.size(), in each iteration:
    • If board[i] == board[i-1], then continue;
    • If i - j > 2, which means we have found more than 2 consecutive balls of the same colours, then make nextStr = board[:j] + board[i:], and return remove(nextStr).
    • Else, set j = i.
  • In the end, just check if i - j > 2, then again make nextStr as described above and return remove with nextStr.
  • Finally, return the string board.
Time Complexity

O(N ^ M), where ‘N’ is the size of the string board, and ‘M’ is the size of the string hand.

 

As we are using recursion and in each function call, we are inserting a string hand character in each position of the string board. Hence the overall time complexity will be O(N ^ M).

Space Complexity

O(N), where ‘N’ is the size of the string board.

 

As we are creating a new string of size N after every insertion in the recursive function. Hence, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Zuma Game
Full screen
Console