【LeetCode 1717. 删除子字符串的最大得分】解析-EW帮帮网

LeetCode中国站原文

https://leetcode.cn/problems/maximum-score-from-removing-substrings/

原始题目

题目描述

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

删除子字符串 "ab" 并得到 x 分。
删除子字符串 "ba" 并得到 y 分。

请返回对 s 字符串执行上面操作若干次能得到的最大得分。

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "ba" (y=5) -> "cdbcbbaaab"
- 删除 "ab" (x=4) -> "cdbcbbaa"
- 删除 "ba" (y=5) -> "cdbcba"
- 删除 "ba" (y=5) -> "cdbc"
总得分: 5 + 4 + 5 + 5 = 19

示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20
解释：
优先删除 "ab" (x=5)，可以删除4次，得到 4 * 5 = 20分。

提示：

$1 <= s.length <= 10^5$
$1 <= x, y <= 10^4$
s 只包含小写英文字母。

讲解

贪心的智慧：解密字符串消除游戏的最大得分

这道题表面上看起来可能组合很多，似乎需要复杂的动态规划，但实际上，它的最优解隐藏在一个非常简洁的贪心策略之中。

第一部分：算法思想 —— 贪心，为何总是对的？

1. 问题的核心：消除的“副作用”

我们有两种消除方式："ab" 和 "ba"。关键在于，消除一个组合，可能会创造出新的消除机会。

比如，对于字符串 "baab"：

如果我们先消除中间的 "aa"（假设有这个规则），会得到 "bb"，游戏结束。
如果我们先消除左边的 "ba"，得到 "ab"，还能再消除一次，获得两次得分。

在这个题目里，消除 "ab" 不会创造出新的 "ba"，反之亦然。但是，消除一个 "ab" 可能会把一个本来被隔开的 b 和 a 连接起来，创造出新的消除机会。例如，在 "b(ab)a" 中，消除 ab 会得到 "ba"。

2. 贪心策略的诞生

既然有两种选择，每次我们应该选哪个？贪心算法告诉我们：哪种选择单位得分高，就优先消除哪种！

让我们来证明一下为什么这个贪心策略是正确的。假设 x > y，即删除 "ab" 的得分更高。我们考虑一个字符串片段，比如 ...b...a...。

贪心策略：我们会优先扫描字符串，把所有能找到的 "ab" 全部删除。这个过程可能会产生一些新的 "ba"。例如，"b(ab)a" 会变成 "ba"。
非贪心策略：假设我们不优先删除 "ab"，而是先删除了一个 "ba"，得到了 y 分。

对比这两种策略：
在一个片段 "aba" 中，

贪心（先删ab）：得到 x 分，剩下 "a"。总分 x。
非贪心（先删ba）：得到 y 分，剩下 "a"。总分 y。
因为 x > y，贪心策略获胜。

在一个片段 "bab" 中，

贪心（先删ab）：得到 x 分，剩下 "b"。总分 x。
非贪心（先删ba）：得到 y 分，剩下 "b"。总分 y。
贪心策略再次获胜。

核心结论：删除得分高的子串（比如"ab"）所能创造出的新的、得分低的子串（"ba"）的机会，永远不会比 先删除得分低的子串所能创造出的新的、得分高的子串的机会更差。因为无论如何，一个 a 和一个 b 最终只能配对一次。优先拿走高分，是稳赚不赔的买卖。

所以，我们的总策略是：

比较 x 和 y 的大小。
第一轮：优先遍历整个字符串，消除所有得分更高的组合（比如 "ab"），并累加得分。
第二轮：在第一轮消除剩下的字符串上，再遍历一次，消除所有得分较低的组合（比如 "ba"），继续累加得分。
返回总得分。

3. 如何高效地“消除”？—— 栈的妙用

我们如何模拟“消除”这个动作呢？如果真的在字符串上反复删除，性能会非常差。

这时，栈（Stack） 数据结构就派上了用场。我们可以把字符串的字符一个个地推入栈中，在推入时进行判断，模拟消除动作。

“消除”流程 (以消除 "ab" 为例):

准备一个空栈（或用 StringBuilder 模拟栈）。
遍历字符串的每个字符 c。
如果 c 是 'b'，并且栈顶的字符是 'a'，那么它们构成了一个 "ab" 组合！
- 我们找到了一个消除机会！立即累加 x 分。
- 将栈顶的 'a' 弹出（相当于一起消除了）。
- 当前的 'b' 也不用入栈了。
否则，不满足消除条件，就把字符 c 正常推入栈中。
遍历结束后，栈中剩下的字符，就是第一轮消除后幸存下来的字符串。

第二部分：代码实现

现在，我们将这个两轮消除的贪心策略，用代码实现出来。

class Solution {
    /**
     * 计算删除子字符串能获得的最大得分。
     * @param s 原始字符串
     * @param x 删除 "ab" 的得分
     * @param y 删除 "ba" 的得分
     * @return 最大总得分
     */
    public int maximumGain(String s, int x, int y) {
        // 贪心策略：始终优先删除得分高的组合。
        // 我们通过比较x和y，来确定哪种组合是“高分组合”，哪种是“低分组合”。
        if (x < y) {
            // 如果删除"ba"得分更高，我们可以巧妙地交换x和y的值，
            // 并翻转整个字符串。这样，我们就可以统一处理逻辑，
            // 始终假设"ab"是高分组合。
            // "ba" 在翻转的字符串中变成了 "ab"。
            int temp = x;
            x = y;
            y = temp;
            s = new StringBuilder(s).reverse().toString();
        }

        // 现在，我们统一认为 x >= y，即 "ab" 是高分组合（或等分）。
        
        // 我们需要一个辅助函数来执行“用栈消除”的逻辑。
        // 这个函数会返回消除后的得分，以及幸存下来的字符串。
        long score = 0;
        
        // 第一轮：贪心，消除所有高分的 "ab"
        StringBuilder remainingAfterFirstPass = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == 'b' && remainingAfterFirstPass.length() > 0 && remainingAfterFirstPass.charAt(remainingAfterFirstPass.length() - 1) == 'a') {
                // 找到了一个 "ab"，得分！
                score += x;
                // 弹出栈顶的 'a'
                remainingAfterFirstPass.deleteCharAt(remainingAfterFirstPass.length() - 1);
            } else {
                // 否则，正常入栈
                remainingAfterFirstPass.append(c);
            }
        }

        // 第二轮：在剩下的字符串上，消除所有低分的 "ba"
        StringBuilder finalRemaining = new StringBuilder();
        for (char c : remainingAfterFirstPass.toString().toCharArray()) {
            if (c == 'a' && finalRemaining.length() > 0 && finalRemaining.charAt(finalRemaining.length() - 1) == 'b') {
                // 找到了一个 "ba"，得分！
                score += y;
                // 弹出栈顶的 'b'
                finalRemaining.deleteCharAt(finalRemaining.length() - 1);
            } else {
                // 正常入栈
                finalRemaining.append(c);
            }
        }
        
        return (int)score;
    }
}

代码精讲与优化

上面的代码逻辑清晰，但可以被优化。我们可以把两轮消除写成一个可复用的辅助函数，让主函数更简洁。

class Solution {
    public int maximumGain(String s, int x, int y) {
        // 保证 x >= y，这样我们总是优先删除 "ab"
        if (x < y) {
            return maximumGain(new StringBuilder(s).reverse().toString(), y, x);
        }

        long totalScore = 0;
        StringBuilder stack1 = new StringBuilder();
        
        // 第一轮：贪心删除所有 "ab"
        for (char c : s.toCharArray()) {
            if (c == 'b' && stack1.length() > 0 && stack1.charAt(stack1.length() - 1) == 'a') {
                totalScore += x;
                stack1.deleteCharAt(stack1.length() - 1);
            } else {
                stack1.append(c);
            }
        }

        // 第二轮：在剩余字符串上删除所有 "ba"
        StringBuilder stack2 = new StringBuilder();
        for (char c : stack1.toString().toCharArray()) {
            if (c == 'a' && stack2.length() > 0 && stack2.charAt(stack2.length() - 1) == 'b') {
                totalScore += y;
                stack2.deleteCharAt(stack2.length() - 1);
            } else {
                stack2.append(c);
            }
        }

        return (int)totalScore;
    }
}

这个优化版本通过一次巧妙的递归调用（或直接交换参数和翻转字符串）统一了处理逻辑，使得代码更加优雅和易于理解。它完美地诠释了如何用贪心思想和栈数据结构，来解决看似复杂的字符串消除问题。

【LeetCode 1717. 删除子字符串的最大得分】解析

目录