Maximum coins by removing the substrings 01 and 10

Updated

Given a string S and two integer X, Y. We can perform only two types of operation any number of times.

  1. Remove a substring “01” from S and earn X coins.
    • For example, S = “951030125″ after removing “01” it becomes “9510325”.
  2. 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.

A stack scanning 761211000101 for the 10 pass, showing the stack and the coin totals 6, 12 and 18 after each of the three pops.

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;
}
Output

21

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)

Comment
Next tutorial
Mithlesh Upadhyay Published 18 Nov 2026 · 4 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials