[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;
    }
}

LeetCode 题目总结