Stack: 1717. Maximum Score From Removing Substrings

This is a biweekly problem and it can be solved by using a stack.

Problem

1717. Maximum Score From Removing Substrings

Basic idea

If x > y, then

step 1: first collect all the valid “ab” and harvest the results. We can do this by using a stack

Step 2: After doing the above step, the rest elements in the stack can only have the following 4 cases:

I) empt.

II) only ‘a’ such as [‘aaaaaaaa’]

III).only ‘b’ such as [“bbbbbb”].

V).both ‘a’ and ‘b’. and **all b must be in front of a** with the pattern as shown in this example [bbbbbbbaaaaaaaaa]. This is tricky, as if not, we will have contraction to step 1. Such as in “aaabbb”, we will have a valid “ab”, it shoud be found in step 1. Or if they are mixed such as “baaabb”, we should also find a valid “ab”. After figuring out this, the results for this case is only the minumu number of (cnt_a, cnt_b) * y.

After figuring out the above case, the code should be not that hard if you are familar with using stacks. The logic can be simplified if we flip the a and b in case of x < y.

Code in C++

class Solution {
public:
    string swap_a_b(string s) {
        string ret = "";
        for (auto x : s) {
            if (x == 'a') ret.push_back('b');
            else if (x == 'b') ret.push_back('a');
            else ret.push_back(x);
        }
        return ret;
    }
    
    int maximumGain(string s, int x, int y) {
        // swap to make the logic easier to be processed
        if (x < y) return maximumGain(swap_a_b(s), y, x);
        s.push_back('x');
        const int n = s.length();
        vector<char> stack;
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'b') {//check whether we can find 'ab'
                if (stack.empty()) stack.push_back(s[i]);
                else {
                    if (stack.back() == 'a') {
                        stack.pop_back();
                        ret += x;
                     } else stack.push_back(s[i]);
                }
            } else if (s[i] == 'a') stack.push_back(s[i]);
            else { // not 'a' or 'b'. The stack will be only the 4 cases mentioned in the explanation
                int cnt_a =0, cnt_b = 0;
                for (auto x : stack) {
                    if (x == 'a') cnt_a++;
                    else cnt_b++;
                }
                ret += min(cnt_a, cnt_b)*y;
                stack.clear();     
            }
        }
        return ret;
    }
};

Informal proof

In step 1, why greedly harvest the “ab” is optimal?
suppose we don’t use the “ab” immediately, and we may have the following 9 cases.
*ab*
left * and be {empty, a, b}, right * can be {empty, a, b}.
The combinations are 9 cases. All those 9 cases are not better than using the “ab” immdiately.

After step 1

• For the case I, II and III, it is easy to shown that we have the optimal solution as we are building everying to “ab” until there is no more a or b to use.
• For the case V, After we reach this case such as [bbbaaa], if we want to get better results, we must build at least one “ab”, it is impossible.