[LeetCode] 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.
For example, when removing “ab” from “cabxbae” it becomes “cxbae”.
Remove substring “ba” and gain y points.
For example, when removing “ba” from “cabxbae” it becomes “cabxe”.
Return the maximum points you can gain after applying the above operations on s.

Example 1:
Input: s = “cdbcbbaaabab”, x = 4, y = 5
Output: 19
Explanation:

• Remove the “ba” underlined in “cdbcbbaaabab”. Now, s = “cdbcbbaaab” and 5 points are added to the score.
• Remove the “ab” underlined in “cdbcbbaaab”. Now, s = “cdbcbbaa” and 4 points are added to the score.
• Remove the “ba” underlined in “cdbcbbaa”. Now, s = “cdbcba” and 5 points are added to the score.
• Remove the “ba” underlined in “cdbcba”. Now, s = “cdbc” and 5 points are added to the score.
  Total score = 5 + 4 + 5 + 5 = 19.

Example 2:
Input: s = “aabbaaxybbaabb”, x = 5, y = 4
Output: 20

Constraints:
1 <= s.length <= 105
1 <= x, y <= 104
s consists of lowercase English letters.

删除子字符串的最大得分。

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

删除子字符串 “ab” 并得到 x 分。
比方说，从 “cabxbae” 删除 ab ，得到 “cxbae” 。
删除子字符串”ba” 并得到 y 分。
比方说，从 “cabxbae” 删除 ba ，得到 “cabxe” 。
请返回对 s 字符串执行上面操作若干次能得到的最大得分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-score-from-removing-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - 栈

这道题总体的思路是贪心，做法一我先给出一个需要用到额外空间的做法。我需要用到两个 stack。首先我预处理一下 input，这样我知道到底是 ab 组合得分更高还是 ba 组合得分更高。接着我开始遍历 input 字符串，我优先处理得分高的组合，比如如果得分高的组合是 ab 的话，当我遇到 ab 这样的子串，我优先处理，然后把它的得分加到 res 中；其他不是 ab 的字母全都加到第一个栈中，记为 stack1。

接着我再从 stack1 中把所有字符串倒出来，因为栈是先进后出的，所以如果一开始我处理的是 ab 的话，那么我现在正好可以处理 ba 这种子串了。注意 ba 从 stack 里倒出来的时候，其实是以 ab 的顺序出来的（这也就是11行和21行判断 first 和 second 的代码是一样的原因）。从 stack1 中弹出的字符我放到另一个栈，记为 stack2。这样我可以利用 stack2 获取到 ba 这种组合同时记录它的得分。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int maximumGain(String s, int x, int y) {
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        int res = 0;
        int max = Math.max(x, y);
        int min = Math.min(x, y);
        char first = (x > y) ? 'a' : 'b';
        char second = (x > y) ? 'b' : 'a';
        for (char c : s.toCharArray()) {
            if (!stack1.isEmpty() && stack1.peek() == first && c == second) {
                stack1.pop();
                res += max;
            } else {
                stack1.push(c);
            }
        }

        while (!stack1.isEmpty()) {
            char c = stack1.pop();
            if (!stack2.isEmpty() && stack2.peek() == first && c == second) {
                stack2.pop();
                res += min;
            } else {
                stack2.push(c);
            }
        }
        return res;
    }
}
// stack

思路二 - 无需额外空间

做法二是一个更优的做法，它不需要额外的空间。我们首先还是需要对得分进行预处理。若 x < y，我们交换 x 和 y，也交换 a 和 b。这意味着：我们总是先处理得分高的组合 a+b。

• 如果 x > y，就先处理 “ab”
• 如果 x < y，就先处理 “ba”

整个代码后续都用变量 a 和 b 处理，和是 “ab” 还是 “ba” 无关。

设两个变量 count1 记录 a 出现的次数，count2 记录 b 出现的次数。开始遍历 input 字符串，如果当前字符是 a，因为我们需要先凑 ab 组合，所以当我们遇到 a 的时候，暂且 count1++，因为只要等到后面有 b 出现的时候，才能将得分最大化。如果当前字符是 b，我们需要判断前面是否有 a 出现过，如果有的话，说明可以凑成 ab 组合，此时我们就将 count1 减一，并将得分加上 x。否则的话，我们就将 count2++，因为我们需要等到后面有 a 出现的时候才能凑成 ba 组合。如果当前字符既不是 a 也不是 b，说明我们到了一个分段点。把当前段里剩下的 a 和 b 尝试做第二优先级的组合（即得分较低的组合），得 y 分；然后把这段配对状态清空（cnt1 = cnt2 = 0）。记得最后还要再做一次计算因为最后一个字符有可能是 a 或 b。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int maximumGain(String s, int x, int y) {
        // corner case
        char a = 'a';
        char b = 'b';
        if (x < y) {
            char temp = a;
            a = b;
            b = a;
            int tempScore = x;
            x = y;
            y = tempScore;
        }

        // normal case
        int count1 = 0;
        int count2 = 0;
        int res = 0;
        for (char c : s.toCharArray()) {
            if (c == a) {
                count1++;
            } else if (c == b) {
                if (count1 > 0) {
                    count1--;
                    res += x;
                } else {
                    count2++;
                }
            } else {
                res += Math.min(count1, count2) * y;
                count1 = 0;
                count2 = 0;
            }
        }
        res += Math.min(count1, count2) * y;
        return res;
    }
}