Maximum Score From Removing Substrings

Maximum Score From Removing Substrings

Maximum Score From Removing Substrings

Problem

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

• Remove the substring "ab" and gain x points.
• Remove the substring "ba" and gain y points.

Return the maximum points you can gain.

Examples

Example 1

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19

• Remove "ba" and get 5 points. Then remove "ab" and get 4 points.
• Then remove "ba" two times and get 5 + 5 points.
• Total = 5 + 4 + 5 + 5 = 19.

Example 2

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

Constraints

• 1 <= s.length <= 10^5
• 1 <= x, y <= 10^4
• s has only lowercase English letters.

Main Idea

This is a greedy problem. The idea is simple: remove the pair with more points first.

• If x >= y, remove all "ab" pairs first. Then remove all "ba" pairs from what is left.
• If y > x, remove all "ba" pairs first. Then remove all "ab" pairs from what is left.

Why does greedy work?

• Only the letters a and b matter. Any other letter works like a wall, because nothing can be removed across it.
• Take a block like "bab". We can remove "ba" (leaving b) or remove "ab" (leaving b). Each choice uses one a, and one b stays.
• In every case, one wrong choice can block a better pair. Taking the higher-value pair first never loses more than it gains.
• After all high-value pairs are gone, the remaining a and b letters are in a fixed form, and the low-value pair is removed from them.

Why a stack?

When a pair is removed, the letters around it can become new neighbors. The stack always holds the last kept letter on top, so we can check it quickly. This is the same idea as in Remove All Adjacent Duplicates.

Solution: Greedy with Stack

We name the letters by the order of the high-value pair:

• first and second are the letters of the high-value pair, in that order.
• If x >= y, the pair is "ab", so first = 'a' and second = 'b'.
• If y > x, the pair is "ba", so first = 'b' and second = 'a'.

var maximumGain = function (s, x, y) {
    let first, second, high, low;

    if (x >= y) {
        first = 'a';
        second = 'b';
        high = x;
        low = y;
    } else {
        first = 'b';
        second = 'a';
        high = y;
        low = x;
    }

    let score = 0;

    // Pass 1: remove the high-value pair ("first" then "second")
    let stack = [];

    for (const ch of s) {
        if (ch === second && stack[stack.length - 1] === first) {
            stack.pop();
            score += high;
        } else {
            stack.push(ch);
        }
    }

    // Pass 2: remove the low-value pair ("second" then "first")
    let stack2 = [];

    for (const ch of stack) {
        if (ch === first && stack2[stack2.length - 1] === second) {
            stack2.pop();
            score += low;
        } else {
            stack2.push(ch);
        }
    }

    return score;
};

How the Code Works

Step 1: Pick the order

• We compare x and y.
• The pair with more points goes first. high is its score, and low is the score of the other pair.

Step 2: First pass

• We read the string from left to right.
• If the current letter is second and the top of the stack is first, we found the high-value pair. We pop and add high.
• Otherwise, we push the letter.
• When the stack is empty, stack[stack.length - 1] is undefined, which never equals a letter, so we push.

Step 3: Second pass

• After pass 1, no high-value pair is left in the stack.
• Now we look for the low-value pair, which is the reverse: second then first.
• If the current letter is first and the top is second, we pop and add low.
• Otherwise, we push the letter.

Step 4: Return the score

• score holds the points from both passes.

Dry Run

Let us take s = "cdbcbbaaabab", x = 4 and y = 5.

Here y > x, so first = 'b', second = 'a', high = 5 and low = 4.

Pass 1 (remove "ba"):

Pass 2 (remove "ab"): The stack is [c, d, b, c, a, b].

• The last two letters are a then b. This is the low-value pair, so we remove it and add 4.
• score = 15 + 4 = 19.

The answer is 19.

Complexity

• Time Complexity: O(n)
  • n is the length of the string.
  • Each pass reads each letter once, and each letter is pushed and popped at most once.
• Space Complexity: O(n)
  • In the worst case, no pair is removed, so a stack holds all n letters.

Comparison

Summary

• Remove the pair with more points first. Then remove the other pair from what is left.
• Letters other than a and b work as walls, and the stack handles them without extra code.
• Pass 1 removes first + second. Pass 2 removes the reverse pair, second + first.
• Each removal can create new neighbors, so a stack is the right tool.
• The solution runs in O(n) time and uses O(n) space.