Maximum Score From Removing Substrings

Leetcode Problem:

• Maximum Score From Removing Substrings

Summary

• Given a string s and two integers x and y, find the maximum points that can be gained by removing substrings of 'ab' and 'ba' from s.

Approach

• The solution uses a two-step approach
• First, it removes all occurrences of 'ab' or 'ba' from the string s, depending on which one has a higher value
• Then, it removes the remaining 'ab' or 'ba' substrings from the resulting string
• The points gained for each step are added to the total score.

Complexity

• O(n), where n is the length of the string s
• This is because the solution makes two passes through the string s, one for each step.

Explain

• The solution starts by initializing two vectors, firstStep and secondStep, to store the characters of the string s after the first and second steps, respectively
• It also initializes the total score res to 0
• The solution then iterates over the string s, adding characters to firstStep and secondStep based on whether they are 'ab' or 'ba'
• If a character is 'ab' or 'ba', the solution checks if the last character in the vector is the same as the character in 'ab' or 'ba'
• If they are the same, the solution adds the points gained for the step to the total score and removes the character from the vector
• Otherwise, the solution adds the character to the vector
• Finally, the solution returns the total score.

Solution Code:

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int res = 0;
        vector firstStep;
        string cmpStr;
        int maxScore = max(x, y);
        int minScore = min(x, y);
        if (x > y){
            cmpStr = "ab";
        } else {
            cmpStr = "ba";
        }

        for(int i = 0 ; i < s.size(); i++){
            if (firstStep.size() == 0 || s[i] != cmpStr[1]){
                firstStep.push_back(s[i]);
            } else {
                char c = firstStep.back();
                if (c == cmpStr[0]){
                    res += maxScore;
                    firstStep.pop_back();
                } else {
                    firstStep.push_back(s[i]);
                }
            }
        }
        vector secondStep;

        for(int i = 0 ; i < firstStep.size(); i++){
            if (secondStep.size() == 0 || firstStep[i] != cmpStr[0]){
                secondStep.push_back(firstStep[i]);
            } else {
                char c = secondStep.back();
                if (c == cmpStr[1]){
                    res += minScore;
                    secondStep.pop_back();
                }else {
                    secondStep.push_back(firstStep[i]);
                }
            }
        }
        return res;
    }
};