Maximum Score From Removing Substrings

Problem Link

https://leetcode.com/problems/maximum-score-from-removing-substrings/description/

Approach

1. If x > y we have to focus on making the "ab" pairs more than any other pair, so we will do the same in the first pass

2. Once all the pairs are done, we will look for the pair "ba" in the remaining string and accordingly add the values to the result

3. The explanation is short and simple but this will take a while to understand please do the dry run 2-4 times

Code

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        stack<char> st1;
        int ans = 0;

        if (x > y) {
            for (char ch : s) {
                if (!st1.empty() && st1.top() == 'a' && ch == 'b') {
                    st1.pop();
                    ans += x;
                } else {
                    st1.push(ch);
                }
            }

            s.clear();
            while (!st1.empty()) {
                s += st1.top();
                st1.pop();
            }
            reverse(s.begin(), s.end());

            for (char ch : s) {
                if (!st1.empty() && st1.top() == 'b' && ch == 'a') {
                    st1.pop();
                    ans += y;
                } else {
                    st1.push(ch);
                }
            }
        } else {
            for (char ch : s) {
                if (!st1.empty() && st1.top() == 'b' && ch == 'a') {
                    st1.pop();
                    ans += y;
                } else {
                    st1.push(ch);
                }
            }

            // Collect remaining characters back into s
            s.clear();
            while (!st1.empty()) {
                s += st1.top();
                st1.pop();
            }
            reverse(s.begin(), s.end());
            for (char ch : s) {
                if (!st1.empty() && st1.top() == 'a' && ch == 'b') {
                    st1.pop();
                    ans += x;
                } else {
                    st1.push(ch);
                }
            }
        }

        return ans;
    }
};

All the best for your DSA journey! Let me know your feedback so that we can improve this article together.

Ujjwal Sharma