1717. Maximum Score From Removing Substrings

leetcode

Problem:

1717 Maximum Score From Removing Substrings

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.
Remove substring "ba" and gain `y` points.

Return the maximum score you can achieve after performing any number of above operations on `s`.

Constraints:

1 <= s.length <= 10⁵
1 <= x, y <= 10⁴
s consists of lowercase English letters.

Solution Description:

To implement the solution, we need to simulate the characters removal process in an optimal way. We should perform the removal of the higher score substring first. This helps in maximizing the score at each step.

Determine the removal order:
- If `x >= y`, remove "ab" first, and then remove "ba".
- If `y > x`, remove "ba" first, and then remove "ab".
Use a stack data structure to facilitate the removal process:
- Iterate through the characters of the string and use stack operations to collect and evaluate substrings for removal.

By processing characters in the optimal removal order and utilising a stack, we ensure a linear time complexity solution with O(n). Space complexity will be O(n) in the worst-case scenario, due to the use of stack.

Example:

Suppose `s = "aabbaaxybbaabb"`, `x = 5`, and `y = 3`.

First, we check `x >= y`, hence we will remove "ab" first.
After each removal, the new string will be evaluated and the next optimal removal step will be performed.
The final score is sum of all the points gained from these steps.

Setup:

Below is the skeleton of the solution using modern JavaScript:

/**
 * Main function to calculate the maximum score by removing substrings.
 * @param {string} s - The input string.
 * @param {number} x - Points for removing "ab".
 * @param {number} y - Points for removing "ba".
 * @returns {number} - The maximum score achieved.
 */
function maximumScore(s, x, y) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    function removeAndCount(s, sub, points) {
        let stack = [];
        let score = 0;
        for (let char of s) {
            stack.push(char);
            // Check the last two characters in the stack
            if (stack.length >= 2 && stack[stack.length - 2] + stack[stack.length - 1] === sub) {
                stack.pop();
                stack.pop();
                score += points;
            }
        }
        return [stack.join(''), score];
    }

    // Determine the order of removal
    let firstSub, firstPoints, secondSub, secondPoints;
    if (x >= y) {
        firstSub = "ab";
        firstPoints = x;
        secondSub = "ba";
        secondPoints = y;
    } else {
        firstSub = "ba";
        firstPoints = y;
        secondSub = "ab";
        secondPoints = x;
    }

    // Remove the first substring
    let [remainingString, firstScore] = removeAndCount(s, firstSub, firstPoints);
    // Remove the second substring from the remaining string
    let [finalString, secondScore] = removeAndCount(remainingString, secondSub, secondPoints);

    // The total score is the sum of both scores
    return firstScore + secondScore;
}

// Test cases
const testCases = [
    { s: "cdbcbbaaabab", x: 4, y: 5, expected: 19 },
];

testCases.forEach((test, index) => {
    const result = maximumScore(test.s, test.x, test.y);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});

Links

Problem:

Solution Description:

Example:

Setup: