LeetCode 题解工作台
删除子字符串的最大得分
给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。 删除子字符串 "ab" 并得到 x 分。 比方说，从 "c ab xbae" 删除 ab ，得到 "cxbae" 。 删除子字符串 "ba" 并得到 y 分。 比方说，从 "cabx ba e" 删除 ba ，得到 "ca…
3
题型
8
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们不妨假设子字符串 "ab" 的得分总是不低于子字符串 "ba" 的得分，如果不是，我们可以交换 "a" 和 "b"，同时交换 和 。 接下来，我们只需要考虑字符串中只包含 "a" 和 "b" 的情况。如果字符串中包含其他字符，我们可以将其视为一个分割点，将字符串分割成若干个只包含 "a" 和 "b" 的子字符串，然后分别计算每个子字符串的得分。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个字符串 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 <= 1051 <= x, y <= 104s只包含小写英文字母。
解题思路
方法一：贪心
我们不妨假设子字符串 "ab" 的得分总是不低于子字符串 "ba" 的得分，如果不是，我们可以交换 "a" 和 "b"，同时交换 和 。
接下来，我们只需要考虑字符串中只包含 "a" 和 "b" 的情况。如果字符串中包含其他字符，我们可以将其视为一个分割点，将字符串分割成若干个只包含 "a" 和 "b" 的子字符串，然后分别计算每个子字符串的得分。
我们观察发现，对于一个只包含 "a" 和 "b" 的子字符串，无论采取什么样的操作，最后一定只剩下一种字符，或者空串。由于每次操作都会同时删除一个 "a" 和一个 "b"，因此总的操作次数一定是固定的。我们可以贪心地先删除 "ab"，再删除 "ba"，这样可以保证得分最大。
因此，我们可以使用两个变量 和 分别记录 "a" 和 "b" 的数量，然后遍历字符串，根据当前字符的不同情况更新 和 ，并计算得分。
对于当前遍历到的字符 ：
- 如果 是 "a"，由于要先删除 "ab"，因此此时我们不消除该字符，只增加 ；
- 如果 是 "b"，如果此时 ，我们可以消除一个 "ab"，并增加 分，否则我们只能增加 ；
- 如果 是其他字符，那么对于该子字符串，我们剩下了 个 "b" 和 个 "a"，我们可以消除 个 "ba"，并增加若干个 分。
遍历结束后，我们还需要额外处理一下剩余的 "ba"，增加若干个 分。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
a, b = "a", "b"
if x < y:
x, y = y, x
a, b = b, a
ans = cnt1 = cnt2 = 0
for c in s:
if c == a:
cnt1 += 1
elif c == b:
if cnt1:
ans += x
cnt1 -= 1
else:
cnt2 += 1
else:
ans += min(cnt1, cnt2) * y
cnt1 = cnt2 = 0
ans += min(cnt1, cnt2) * y
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Expect candidates to identify the greedy priority for substring removal.
- question_mark
Look for stack-based state management instead of repeated string replacements.
- question_mark
Watch for handling overlapping substrings efficiently.
常见陷阱
外企场景- error
Removing substrings in the wrong order reduces the maximum achievable score.
- error
Using repeated string scanning instead of a stack leads to O(n^2) runtime.
- error
Failing to handle overlapping patterns causes missed removals.
进阶变体
外企场景- arrow_right_alt
Consider the case where multiple substring types exist with different point values and overlapping occurrences.
- arrow_right_alt
Modify the problem to handle longer patterns like "abc" and "cba" with distinct scores.
- arrow_right_alt
Handle streaming input where characters arrive sequentially, requiring online stack-based processing.