删除子字符串的最大得分

难度: 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⁵
1 <= x, y <= 10⁴
s 只包含小写英文字母。

Submission

运行时间: 167 ms

内存: 16.4 MB

import re

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        cnt_a, cnt_b, res = 0, 0, 0
        s = s + '-'
        for c in s:
            if c == 'b':
                if x >= y and cnt_a > 0:    # ab 的情况
                    res += x
                    cnt_a -= 1
                else:
                    cnt_b += 1
            elif c == 'a':
                if y > x and cnt_b > 0:     # ba 的情况
                    res += y
                    cnt_b -= 1
                else:
                    cnt_a += 1
            else:                           #这一个窗口截止了
                if cnt_a > 0 and cnt_b > 0:
                    res += min(x, y) * min(cnt_a, cnt_b)
                cnt_a = 0
                cnt_b = 0
        
        return res

Explain

这个解法主要通过一次遍历来优先删除得分更高的子字符串。首先，通过比较x和y的大小来决定优先删除哪种子字符串（'ab'或'ba'）。如果x >= y，则优先删除'ab'；反之，优先删除'ba'。遍历字符串s的每一个字符，用cnt_a和cnt_b分别记录当前未匹配的'a'和'b'的数量。当遇到'b'时，如果x >= y并且之前有未匹配的'a'，则删除'ab'并累加得分x；否则，增加'b'的计数。当遇到'a'时，如果y > x并且之前有未匹配的'b'，则删除'ba'并累加得分y；否则，增加'a'的计数。如果遇到非'a'或'b'的字符，此时检查并处理剩余的'a'和'b'，能组成多少对就删除多少对，并根据x和y的较小值累加得分。通过这种方法，可以在一次遍历中处理所有可能的得分并达到最大化。

时间复杂度: O(n)

空间复杂度: O(1)

import re

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        cnt_a, cnt_b, res = 0, 0, 0  # 初始化计数器和结果变量
        s = s + '-'  # 添加结尾标志以便处理最后一组字符
        for c in s:
            if c == 'b':
                if x >= y and cnt_a > 0:    # 如果优先删除'ab'且存在未匹配的'a'
                    res += x  # 删除'ab'并加分
                    cnt_a -= 1  # 减少'a'计数
                else:
                    cnt_b += 1  # 增加'b'计数
            elif c == 'a':
                if y > x and cnt_b > 0:     # 如果优先删除'ba'且存在未匹配的'b'
                    res += y  # 删除'ba'并加分
                    cnt_b -= 1  # 减少'b'计数
                else:
                    cnt_a += 1  # 增加'a'计数
            else:                           # 遇到非'a'或'b'的字符，处理剩余字符
                if cnt_a > 0 and cnt_b > 0:
                    res += min(x, y) * min(cnt_a, cnt_b)  # 删除剩余的'a'和'b'对
                cnt_a = 0  # 重置'a'计数
                cnt_b = 0  # 重置'b'计数
        
        return res  # 返回最终得分

Explore

这种策略基于贪心算法的思想，即在每一步中都尝试做出当前看起来最优的选择，以达到局部最优解。在本题中，算法通过判断当前字符与累积字符的匹配来实时决策删除，这样可以在一次遍历中快速计算出最大得分，而不需要考虑全局的字符序列。虽然这种方法可能不会得到全局最优解，但它保证了算法的效率和简便性。

添加结尾标志'-'的目的是为了确保在字符串末尾时能够处理所有剩余的'a'和'b'，使得算法能正确地处理到最后的字符。这种方法不会影响原有的计数逻辑，因为'-'字符在处理逻辑中只起到触发结算的作用，并不参与'a'或'b'的计数。因此，无论原字符串以何种字符结尾，这种处理都不会导致最后一个字符被错误地忽略或错误计数。

该处理方式是有效的，因为它确保了每次遇到非'a'或'b'的字符时，都对之前累积的'a'和'b'进行结算，以清空计数器。这意味着每个非'a'或'b'的字符都像一个分割点，强制算法结算前面的子字符串。如果字符串结束时有大量未匹配的'a'和'b'，这种方法仍然有效，因为结尾标志'-'将触发最后一次必要的结算。

虽然重置操作可能看似会错过某些删除机会，但在这种实现中，每次遇到非'a'或'b'的字符时，重置前都会尝试将当前累积的'a'和'b'尽可能匹配并删除，这保证了在每个分段内部'a'和'b'都得到了有效处理。因此，即使'a'和'b'的分布是间断的，每段内部的处理仍然尽可能地优化得分，不会因为重置操作而错过删除子字符串的机会。这种方法保持了算法的高效性和简洁性。