Medium

题目描述

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

  • 删除子字符串 "ab" 并得到 x 分。
    • 例如，从 "cabxbae" 删除 ab，得到 "cxbae"。
  • 删除子字符串 "ba" 并得到 y 分。
    • 例如，从 "cabxbae" 删除 ba，得到 "cabxe"。

请返回在字符串 s 上执行上述操作若干次能够获得的最大分数。

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加下划线的 "ba"。现在 s = "cdbcbbaaab"，分数增加 5 分。
- 删除 "cdbcbbaaab" 中加下划线的 "ab"。现在 s = "cdbcbbaa"，分数增加 4 分。
- 删除 "cdbcbbaa" 中加下划线的 "ba"。现在 s = "cdbcba"，分数增加 5 分。
- 删除 "cdbcba" 中加下划线的 "ba"。现在 s = "cdbc"，分数增加 5 分。
总分数 = 5 + 4 + 5 + 5 = 19。

示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20

约束条件：

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

解题思路

这是一个贪心策略问题。核心思路是优先移除得分更高的子字符串。

分析：

  1. 我们有两种操作：“ab” 得 x 分，“ba” 得 y 分
  2. 关键洞察：应该优先处理得分更高的子字符串，因为先处理高分的不会影响低分的机会
  3. 如果 x > y，优先移除 “ab”；否则优先移除 “ba”

算法步骤：

  1. 比较 x 和 y 的大小，确定优先处理的子字符串
  2. 使用栈（或字符串）进行第一轮处理：
    • 遍历字符串，如果当前字符与栈顶字符能组成高优先级子字符串，则移除并加分
    • 否则将当前字符入栈
  3. 对第一轮处理后的结果，再进行第二轮处理，移除剩余的另一种子字符串

时间复杂度： O(n)，每个字符最多被处理两次 空间复杂度： O(n)，栈的空间

这种方法保证了得到最大分数，因为贪心策略确保我们不会错过任何可能的高分组合。

代码实现

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        // 确保 x >= y，如果不是则交换
        if (x < y) {
            swap(x, y);
            // 同时交换对应的字符
            for (char& c : s) {
                if (c == 'a') c = 'b';
                else if (c == 'b') c = 'a';
            }
        }
        
        int score = 0;
        
        // 第一轮：移除 "ab"（高分）
        string stack;
        for (char c : s) {
            if (!stack.empty() && stack.back() == 'a' && c == 'b') {
                stack.pop_back();
                score += x;
            } else {
                stack.push_back(c);
            }
        }
        
        // 第二轮：移除 "ba"（低分）
        string result;
        for (char c : stack) {
            if (!result.empty() && result.back() == 'b' && c == 'a') {
                result.pop_back();
                score += y;
            } else {
                result.push_back(c);
            }
        }
        
        return score;
    }
};

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        # 确保优先处理高分的子字符串
        if x < y:
            x, y = y, x
            s = s.replace('a', 'c').replace('b', 'a').replace('c', 'b')
        
        score = 0
        
        # 第一轮：移除 "ab"（高分）
        stack = []
        for c in s:
            if stack and stack[-1] == 'a' and c == 'b':
                stack.pop()
                score += x
            else:
                stack.append(c)
        
        # 第二轮：移除 "ba"（低分）
        result = []
        for c in stack:
            if result and result[-1] == 'b' and c == 'a':
                result.pop()
                score += y
            else:
                result.append(c)
        
        return score

public class Solution {
    public int MaximumGain(string s, int x, int y) {
        // 确保 x >= y
        if (x < y) {
            (x, y) = (y, x);
            s = s.Replace('a', 'c').Replace('b', 'a').Replace('c', 'b');
        }
        
        int score = 0;
        
        // 第一轮：移除 "ab"（高分）
        var stack = new List<char>();
        foreach (char c in s) {
            if (stack.Count > 0 && stack[stack.Count - 1] == 'a' && c == 'b') {
                stack.RemoveAt(stack.Count - 1);
                score += x;
            } else {
                stack.Add(c);
            }
        }
        
        // 第二轮：移除 "ba"（低分）
        var result = new List<char>();
        foreach (char c in stack) {
            if (result.Count > 0 && result[result.Count - 1] == 'b' && c == 'a') {
                result.RemoveAt(result.Count - 1);
                score += y;
            } else {
                result.Add(c);
            }
        }
        
        return score;
    }
}

var maximumGain = function(s, x, y) {
    // 确保优先处理高分的子字符串
    if (x < y) {
        [x, y] = [y, x];
        s = s.replace(/a/g, 'c').replace(/b/g, 'a').replace(/c/g, 'b');
    }
    
    let score = 0;
    
    // 第一轮：移除 "ab"（高分）
    let stack = [];
    for (let c of s) {
        if (stack.length > 0 && stack[stack.length - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个字符最多被处理两次，n为字符串长度
空间复杂度O(n)栈空间最坏情况下存储所有字符

相关题目