1717. Maximum Score From Removing Substrings

Problem

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

Remove substring `"ab"` and gain `x` points.

• For example, when removing "ab" from "cabxbae" it becomes "cxbae".

  Remove substring "ba" and gain y points.

• For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

  Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

  Constraints:

• 1 <= s.length <= 105

• 1 <= x, y <= 104

• s consists of lowercase English letters.

Solution 1

/**
 * @param {string} s
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var maximumGain = function(s, x, y) {
    var stack = [];
    var score = 0;
    var a = x > y ? 'ab' : 'ba';
    var b = x > y ? 'ba' : 'ab';
    var ax = x > y ? x : y;
    var bx = x > y ? y : x;
    var score = 0;
    for (var i = 0; i < s.length; i++) {
        if (stack[stack.length - 1] === a[0] && s[i] === a[1]) {
            stack.pop();
            score += ax;
        } else {
            stack.push(s[i]);
        }
    }
    s = stack.join('');
    stack = [];
    for (var i = 0; i < s.length; i++) {
        if (stack[stack.length - 1] === b[0] && s[i] === b[1]) {
            stack.pop();
            score += bx;
        } else {
            stack.push(s[i]);
        }
    }
    return score;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

Solution 2

/**
 * @param {string} s
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var maximumGain = function(s, x, y) {
    if (y > x) {
        return maximumGain(s.split('').reverse(), y, x);
    }
    var aCount = 0;
    var bCount = 0;
    var score = 0;
    for (var i = 0; i <= s.length; i++) {
        if (s[i] === 'a') {
            aCount += 1;
        } else if (s[i] === 'b') {
            if (aCount > 0) {
                aCount -= 1;
                score += x;
            } else {
                bCount += 1;
            }
        } else {
            score += Math.min(aCount, bCount) * y;
            aCount = 0;
            bCount = 0;
        }
    }
    return score;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).