Maximum Score From Removing Substrings

Medium
402.

Maximum Score From Removing Substrings

Maximum Score From Removing Substrings is a medium coding problem on strings, greedy and stack, asked in Amazon and Google interviews.

You are given a string s and two integers x and y. You may repeatedly:

  • remove the substring "ab" and gain x points, or
  • remove the substring "ba" and gain y points.

Return the maximum total score obtainable.

Example 1

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

Example 2

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

Example 3

Input
s = "ab", x = 1, y = 10
Output
1

Constraints

  • 1 <= s.length <= 40
  • 1 <= x, y <= 10000
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var maximumGain = function(s, x, y) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Score From Removing Substrings — Problem & Solution

Maximum Score From Removing Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Score From Removing Substrings is a medium coding problem on strings, greedy and stack, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy, Stack
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s and two integers x and y. You may repeatedly:

  • remove the substring "ab" and gain x points, or
  • remove the substring "ba" and gain y points.

Return the maximum total score obtainable.

Example 1

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

Example 2

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

Example 3

Input: s = "ab", x = 1, y = 10
Output: 1

Constraints

  • 1 <= s.length <= 40
  • 1 <= x, y <= 10000
  • s consists of lowercase English letters.

Hints for Maximum Score From Removing Substrings

  1. Hint 1

    Removing the higher-scoring pair first is never worse — any ab and ba that compete for the same letters can be reordered without loss.

  2. Hint 2

    So sweep once with a stack removing the better pair, then sweep the leftover string removing the other.

  3. Hint 3

    Letters that are neither a nor b simply block matches and stay on the stack.

How to solve Maximum Score From Removing Substrings

Remove the higher-scoring pair greedily first with a stack, then sweep the leftover removing the other pair.

Approach

  1. Pick first as the pair with the larger score.
  2. Sweep s with a stack popping and scoring whenever top + ch == first.
  3. Sweep the remaining string the same way for the other pair.

Why it works

Whenever an ab and a ba compete for the same letters, taking the more valuable one never reduces the total number of pairs removable, so greedy by value is optimal; each sweep removes every pair reachable after cancellations.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Letters other than a/b stay on the stack and separate segments.

Reference solution

Python

def maximumGain(s: str, x: int, y: int) -> int:
    first = "ab" if x >= y else "ba"
    second = "ba" if x >= y else "ab"
    total = 0

    def sweep(text, pair, score):
        nonlocal total
        stack = []
        for ch in text:
            if stack and stack[-1] == pair[0] and ch == pair[1]:
                stack.pop()
                total += score
            else:
                stack.append(ch)
        return "".join(stack)

    rest = sweep(s, first, max(x, y))
    sweep(rest, second, min(x, y))
    return total

Java

private static int gainTotal;

private static String gainSweep(String text, char first, char second, int score) {
    StringBuilder stack = new StringBuilder();
    for (int i = 0; i < text.length(); i++) {
        char c = text.charAt(i);
        if (stack.length() > 0 && stack.charAt(stack.length() - 1) == first && c == second) {
            stack.deleteCharAt(stack.length() - 1);
            gainTotal += score;
        } else {
            stack.append(c);
        }
    }
    return stack.toString();
}

public static int maximumGain(String s, int x, int y) {
    gainTotal = 0;
    if (x >= y) {
        String rest = gainSweep(s, 'a', 'b', x);
        gainSweep(rest, 'b', 'a', y);
    } else {
        String rest = gainSweep(s, 'b', 'a', y);
        gainSweep(rest, 'a', 'b', x);
    }
    return gainTotal;
}

C++

static int gainTotal;

static string gainSweep(const string& text, char first, char second, int score) {
    string stk;
    for (char c : text) {
        if (!stk.empty() && stk.back() == first && c == second) {
            stk.pop_back();
            gainTotal += score;
        } else {
            stk.push_back(c);
        }
    }
    return stk;
}

int maximumGain(string s, int x, int y) {
    gainTotal = 0;
    if (x >= y) {
        string rest = gainSweep(s, 'a', 'b', x);
        gainSweep(rest, 'b', 'a', y);
    } else {
        string rest = gainSweep(s, 'b', 'a', y);
        gainSweep(rest, 'a', 'b', x);
    }
    return gainTotal;
}

JavaScript

var maximumGain = function(s, x, y) {
    const first = x >= y ? "ab" : "ba";
    const second = x >= y ? "ba" : "ab";
    let total = 0;
    const sweep = function(input, pair, score) {
        const stack = [];
        for (let i = 0; i < input.length; i++) {
            if (stack.length > 0 && stack[stack.length - 1] === pair.charAt(0) && input.charAt(i) === pair.charAt(1)) {
                stack.pop();
                total += score;
            } else {
                stack.push(input.charAt(i));
            }
        }
        return stack.join("");
    };
    const rest = sweep(s, first, Math.max(x, y));
    sweep(rest, second, Math.min(x, y));
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms