Given a string S and two integer X, Y. We can perform only two types of operation any number of times.
- Remove a substring “01” from S and earn X coins.
- For example, S = “951030125″ after removing “01” it becomes “9510325”.
- Remove a substring “10” from S and earn Y coins.
- For example, S = “951030125″ after removing “10” it becomes “9530125”.
Find the maximum number of coins we can get after performing above operations any number of times.
Examples :
Input : S = "761211000101", X = 3, Y = 6. Output : 21 Explanation : Remove underlined "10" from "761211000101", and gain Y coins. Now, S ="7612100101", Coins = 6. Remove underlined "10" from "7612100101", and gain Y coins. Now, S = "76120101", Coins = 12. Remove underlined "10" from "76120101", and gain Y coins. Now, S = "761201", Coins = 18. Finally, Remove "01" from "761201", and gain X coins. Now, S = "7612", Coins = 21. Now, no other valid substring can be chosen. Thus, the max Coins gained is 21. Input : S = "101010", X = 10, Y = 11. Output : 33
It seems like an optimization problem, but Greedy solution works fine.
The deciding factor for the removal of the substring “01” or “10” purely depends upon the values of X and Y.
If X > Y, it makes more sense to remove all “01” before removing “10”. Similarly, if Y > X, removing all “10” will be the best option to go with.
Approach :
1. Using Stack
Maintain a stack data structure for storing the characters of the string S. Let us assume X > Y, keep pushing all the characters except ‘1’ to the stack. If we encounter ‘1’ and the top of the stack contains ‘0’, we have found a substring “01” so perform a pop operation and add X coins to your total coins. Repeat till the end of the string.

Now generate a new string S’ from the remaining characters in the stack, and reverse it ( S’ = reverse(S’) ).
Perform the above step for substring “10”, and add Y coins to your total coins.
Implementation :
#include <bits/stdc++.h>
using namespace std;
int getCoins(string& s, stack<char>& st, int val, string subString){
// it holds the running sum
int coins = 0;
// traverse through the given string
for (int i = 0; i < s.size(); i++) {
if (st.empty()) {
st.push(s[i]);
}
/* lets say subString is "01", and we encounter '1'
and stack has '0' in its top, add val to coins
and remove the '0' from stack. */
else if (s[i] == subString[1] && st.top() == subString[0]) {
st.pop();
coins += val;
}
else {
st.push(s[i]);
}
}
return coins;
}
int getMaxCoins(string s, int X, int Y)
{
// It holds the total coins earned.
int totalCoins = 0;
// It hold the characters of the string s.
stack<char> st;
// removing all "01" before removing any "10" is more
// profitable.
if (X > Y) {
// getCoins() will return the coins that can be
// earned by removing all "01"
totalCoins += getCoins(s, st, X, "01");
// s2 will be the new string after removal of all
// "01"
string s2 = "";
while (!st.empty()) {
s2 += st.top();
st.pop();
}
// reverse the string as, stack holds data in LIFO
// format
reverse(s2.begin(), s2.end());
// this function call will return the coins gained
// by removing "10"
totalCoins += getCoins(s2, st, Y, "10");
}
else { // removing all "10" before removing any "01" is
// more profitable.
// earn Y coins by removing each instances of 01
totalCoins += getCoins(s, st, Y, "10");
string s2 = "";
while (!st.empty()) {
s2 += st.top();
st.pop();
}
reverse(s2.begin(), s2.end());
// similarly, get X coins by removing "01"
totalCoins += getCoins(s2, st, X, "01");
}
return totalCoins;
}
// Driver Code
int main()
{
// S is the given input string
string s = "761211000101";
// X is the coins earned by removing "01"
// Y is the coins earned by removing "10"
int X = 3, Y = 6;
// getMaxCoins() will get the maximum coins by
// performing the operations on S.
cout << getMaxCoins(s, X, Y) << endl;
return 0;
}
Complexities
Time: O(n) (where n = S.length(). To be precise O(2n), when the given string S does not contain any “01” or “10” we will be traversing the string 2 times)
Space: O(n)