Maximum Score From Removing Substrings

Medium Stack Stack Basics Original on LeetCode

Reported atSwiggyJuspay

Maximum Score From Removing Substrings is a medium stack problem solved with the stack basics pattern. The best approach, optimal (greedy with two stack passes), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every removal) up.

Problem

You are given a string s and two integers x and y. You may repeat either of these moves as often as you like:

  • Delete a substring "ab" from s and earn x points.
  • Delete a substring "ba" from s and earn y points.

After a deletion, the remaining characters close the gap, so new pairs can form. Return the maximum total number of points you can earn.

Examples

Example 1

Input
s = "xbaabay", x = 4, y = 6
Output
12
Why
Remove "ba" to get "xabay" (+6), then remove "ba" again to get "xay" (+6).

Example 2

Input
s = "abab", x = 2, y = 3
Output
5
Why
Remove the middle "ba" (+3), which leaves "ab" (+2). Removing "ab" first would only allow 2 + 2 = 4.

Example 3

Input
s = "kbbaxaab", x = 5, y = 1
Output
6
Why
The 'x' splits the string. "kbba" gives one "ba" (+1) and "aab" gives one "ab" (+5).

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every removal)O(2ⁿ · n)O(2ⁿ · n)
Optimal (greedy with two stack passes)O(n)O(n)

1Brute force (try every removal)

TimeO(2ⁿ · n)The number of distinct intermediate strings can grow exponentially, and each one is scanned and copied in O(n).
SpaceO(2ⁿ · n)The memo stores every distinct intermediate string.

Explore every possible order of removals. From a string, try deleting each occurrence of "ab" or "ba", recurse on the shorter string, and keep the best total. Memoize on the string so repeated states are solved once.

  1. best(t) = 0 if t contains neither pair.
  2. Otherwise, for each index i where t[i..i+1] is "ab" (or "ba"), consider x (or y) + best(t without those two letters).
  3. Return the maximum, caching the answer for t.
class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    private int x, y;

    public int maximumGain(String s, int x, int y) {
        this.x = x;
        this.y = y;
        return best(s);
    }

    private int best(String t) {
        Integer cached = memo.get(t);
        if (cached != null) return cached;
        int res = 0;
        for (int i = 0; i + 1 < t.length(); i++) {
            char c = t.charAt(i), d = t.charAt(i + 1);
            String rest = null;
            int gain = 0;
            if (c == 'a' && d == 'b') gain = x;
            else if (c == 'b' && d == 'a') gain = y;
            if (gain > 0) {
                rest = t.substring(0, i) + t.substring(i + 2);
                res = Math.max(res, gain + best(rest));
            }
        }
        memo.put(t, res);
        return res;
    }
}

2Optimal (greedy with two stack passes)

TimeO(n)Each pass pushes and pops each character at most once.
SpaceO(n)The two stacks hold up to n characters.

Inside a block of only 'a' and 'b', the number of pairs you can remove in total is fixed (the smaller letter count), so you want as many of the valuable pair as possible. Removing the valuable pair first never blocks another valuable one. Run a stack pass that deletes every valuable pair (top is its first letter and the current char is its second), then run a second stack pass on the leftover string that deletes the cheaper pair.

  1. Let first/second be the letters of the more valuable pair ("ab" if x >= y, else "ba"), with values hi and lo.
  2. Pass 1: push characters onto a stack; when the current char is second and the top is first, pop and add hi.
  3. Pass 2: scan the leftover stack contents the same way, removing the reversed pair (second then first) and adding lo.
  4. Return the total.
class Solution {
    public int maximumGain(String s, int x, int y) {
        char first = 'a', second = 'b';
        int hi = x, lo = y;
        if (x < y) {
            first = 'b';
            second = 'a';
            hi = y;
            lo = x;
        }
        int score = 0;
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == second && st.length() > 0 && st.charAt(st.length() - 1) == first) {
                st.deleteCharAt(st.length() - 1);
                score += hi;
            } else {
                st.append(c);
            }
        }
        StringBuilder st2 = new StringBuilder();
        for (int i = 0; i < st.length(); i++) {
            char c = st.charAt(i);
            if (c == first && st2.length() > 0 && st2.charAt(st2.length() - 1) == second) {
                st2.deleteCharAt(st2.length() - 1);
                score += lo;
            } else {
                st2.append(c);
            }
        }
        return score;
    }
}

Edge cases to test

  • x == y: every removable pair is worth the same
  • Removing one pair glues its neighbours together and can create a new pair
  • Letters other than 'a' and 'b' act as walls that no pair can cross
  • No 'a' or no 'b' at all: the answer is 0

Hints

Hint 1

Removing a pair can only create new pairs from its neighbours. Does it ever hurt to grab the more valuable pair first?

Hint 2

Greedily remove every copy of the more valuable pair, then every copy of the other pair in what remains.

Hint 3

A stack removes all copies of a two-letter pattern in one pass, including the ones that appear after earlier removals.

FAQ

What is the best time complexity for Maximum Score From Removing Substrings?

Optimal (greedy with two stack passes) runs in O(n) time and O(n) extra space. Each pass pushes and pops each character at most once.

Which pattern does Maximum Score From Removing Substrings use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Is there a brute force solution for Maximum Score From Removing Substrings?

Yes. Brute force (try every removal) takes O(2ⁿ · n) time and O(2ⁿ · n) space. Explore every possible order of removals.

Which edge cases should I test for Maximum Score From Removing Substrings?

x == y: every removable pair is worth the same; Removing one pair glues its neighbours together and can create a new pair; Letters other than 'a' and 'b' act as walls that no pair can cross; No 'a' or no 'b' at all: the answer is 0.