Maximum Score From Removing Substrings

medium array greedy stack

Problem

You are given a string s made of lowercase letters and two integers x and y. You may repeatedly delete a substring "ab" to earn x points, or delete a substring "ba" to earn y points. After each deletion the remaining characters join together, which can create new "ab" or "ba" pairs. Return the maximum total points you can collect.

Inputs = "cdbcbbaaabab", x = 4, y = 5

Output19

Since y > x, remove every "ba" first (worth 5 each), then every "ab" (worth 4 each). Three "ba" removals (+5 each) and one leftover "ab" removal (+4) give 5 + 5 + 5 + 4 = 19.

s (lowercase letters)

x (for "ab")

y (for "ba")

def maximum_gain(s, x, y):
    a, b = ('a', 'b', x), ('b', 'a', y)
    if x < y:
        a, b = b, a
    score = 0
    score += sweep(s, a)
    s = leftover(s, a)
    score += sweep(s, b)
    return score

function maximumGain(s, x, y) {
  let a = ['a', 'b', x], b = ['b', 'a', y];
  if (x < y) { [a, b] = [b, a]; }
  let score = 0;
  score += sweep(s, a);
  s = leftover(s, a);
  score += sweep(s, b);
  return score;
}

class Solution {
    public int maximumGain(String s, int x, int y) {
        char f1 = 'a', s1 = 'b'; int v1 = x, v2 = y;
        if (x < y) { f1 = 'b'; s1 = 'a'; v1 = y; v2 = x; }
        int score = 0;
        score += sweep(s, f1, s1, v1);
        s = leftover(s, f1, s1);
        score += sweep(s, swap(f1), swap(s1), v2);
        return score;
    }
}

int maximumGain(string s, int x, int y) {
    char f = 'a', g = 'b'; int v1 = x, v2 = y;
    if (x < y) { f = 'b'; g = 'a'; v1 = y; v2 = x; }
    int score = 0;
    score += sweep(s, f, g, v1);
    s = leftover(s, f, g);
    score += sweep(s, g, f, v2);
    return score;
}

Explanation

This is a greedy problem. Every time we delete a pair we earn either x (for "ab") or y (for "ba"). The key insight is that removing one pair can never block us from removing the other pair later — so we should always grab the more valuable pair first, as many times as possible, and only then collect the cheaper one from what is left.

Suppose y > x. We sweep the string left to right with a stack. For each character, if the top of the stack is 'b' and the current character is 'a', the two form "ba": we pop the 'b', skip pushing, and add y to the score. Otherwise we push the character. By the time we finish, every "ba" that could ever appear has been removed.

Then we do a second stack pass over whatever characters remain, this time matching the cheaper "ab" pair and adding x for each one removed.

Trace with s = "cdbcbbaaabab", x = 4, y = 5. Because y is bigger, we hunt for "ba" first. Two "ba" pairs collapse during the first sweep (+5 and +5), and as the string compresses a third "ba" appears and collapses (+5). The leftover characters then yield one "ab" pair in the second sweep (+4). Total = 5 + 5 + 5 + 4 = 19.

The stack guarantees we always match the closest valid neighbours, and the two passes together extract every possible pair, so the greedy total is optimal.

Time: O(n) Space: O(n)