Find Maximum Score of Bit Removal Game in C++

Suppose we have a binary string S with n bits. Amal and Bimal are playing a game. Amal moves first, then Bimal, and they move alternatively. During their move, the player can select any number (not less than one) of consecutive equal characters in S and remove them. After the characters are removed, the characters to the left side and to the right side of the removed block become adjacent. The game ends when the string becomes empty, and the score of each player will be the number of 1-characters deleted by them. They both wants to maximize their score. We have to find the resulting score of Amal.

Problem Category

To solve this problem, we need to manipulate strings. Strings in a programming language are a stream of characters that are stored in a particular array-like data type. Several languages specify strings as a specific data type (eg. Java, C++, Python); and several other languages specify strings as a character array (eg. C). Strings are instrumental in programming as they often are the preferred data type in various applications and are used as the datatype for input and output. There are various string operations, such as string searching, substring generation, string stripping operations, string translation operations, string replacement operations, string reverse operations, and much more. Check out the links below to understand how strings can be used in C/C++.

https://www.tutorialspoint.com/cplusplus/cpp_strings.htm

https://www.tutorialspoint.com/cprogramming/c_strings.htm

So, if the input of our problem is like S = "01111001", then the output will be 4.

Steps

To solve this, we will follow these steps −

n := size of S
Define an array c of size: 150 and filled with 0
num := 0
c1 := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   if S[i] is same as '1', then:
      (increase num by 1)
   Otherwise
      c[c1] := num
      increase c1 by 1
      num := 0
c[c1] := num and increase c1 by 1
sort the array c up to next c1 positions
sum := 0
for initialize i := c1 - 1, when i >= 0, update i = i - 2, do:
   sum := sum + c[i]
return sum

Example

Let us see the following implementation to get better understanding −

#include <bits/stdc++.h>
using namespace std;
int solve(string S){
   int n = S.size();
   int c[150] = { 0 };
   int num = 0;
   int c1 = 0;
   for (int i = 0; i < n; i++){
      if (S[i] == '1')
         num++;
      else{
         c[c1++] = num;
         num = 0;
      }
   }
   c[c1++] = num;
   sort(c, c + c1);
   int sum = 0;
   for (int i = c1 - 1; i >= 0; i = i - 2){
      sum = sum + c[i];
   }
   return sum;
}
int main(){
   string S = "01111001";
   cout << solve(S) << endl;
}

Input

"01111001"

Output

4