删除子字符串的最大得分 图解题解
这道题到底在问什么
- 输入
- s = "abbaab", x = 4, y = 5
- 输出
- 14(先删 2 个 "ba" 得 10 分,再删 1 个 "ab" 得 4 分)
- 输入
- s = "cdbcbbaaabab", x = 4, y = 5
- 输出
- 19(原题示例,删法不唯一,但最大分固定)
最优解：一步一步想明白
- 3记牢这句:分高的那对先用一遍栈删光,剩下的串再用一遍栈删另一对,两遍得分相加。下面每一帧都在套它。
- 4看舞台。上面一排是要扫的字符串 "abbaab",下面这根竖栈一会儿会把暂时删不掉的字符摞起来。因为 "ba" 值 5 分、"ab" 值 4 分,我们定下计划:第一遍只盯着删 "ba",第二遍再回收 "ab"。指针还没出发,栈是空的,总分 0。
- 5第一遍正式开始。这一遍眼里只有高分对 "ba"。规则很简单:栈顶是 "b"、当前字符是 "a",就说明它俩贴在一起能凑成 "ba",弹掉栈顶那个 "b"、和当前的 "a" 一起消掉,加 5 分;凑不成就把当前字符压进栈,留着以后看。
- 6指针走到第 0 位,是 "a"。现在栈顶是 空的。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "a" 压进栈。
- 7凑不成 "ba"(栈本来是空的),所以把 "a" 压进栈,先存着。总分还是 0。
- 8指针走到第 1 位,是 "b"。现在栈顶是 "a"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "b" 压进栈。
- 9凑不成 "ba"(栈顶不是 "b" 或当前不是 "a"),所以把 "b" 压进栈,先存着。总分还是 0。
- 10指针走到第 2 位,是 "b"。现在栈顶是 "b"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "b" 压进栈。
- 11凑不成 "ba"(栈顶不是 "b" 或当前不是 "a"),所以把 "b" 压进栈,先存着。总分还是 0。
- 12指针走到第 3 位,是 "a"。现在栈顶是 "b"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "a" 压进栈。
- 13栈顶 "b" 配上当前 "a",正好是一个 "ba",消掉这一对,加 5 分,总分变成 5。栈顶那个 "b" 被弹走,栈矮了一层。
- 14指针走到第 4 位,是 "a"。现在栈顶是 "b"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "a" 压进栈。
- 15栈顶 "b" 配上当前 "a",正好是一个 "ba",消掉这一对,加 5 分,总分变成 10。栈顶那个 "b" 被弹走,栈矮了一层。
- 16指针走到第 5 位,是 "b"。现在栈顶是 "a"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "b" 压进栈。
- 17凑不成 "ba"(栈顶不是 "b" 或当前不是 "a"),所以把 "b" 压进栈,先存着。总分还是 10。
- 18第一遍扫到头了。一路上凑成了 2 个 "ba",每个 5 分,拿下 10 分。栈里现在剩 "ab",这就是删光所有 "ba" 之后删不动的残串。接下来把这段残串拿去做第二遍。
- 19第二遍开始。舞台上排换成了第一遍剩下的 "ab"。这一遍改盯低分对 "ab":栈顶是 "a"、当前是 "b",就凑成 "ab" 消掉、加 4 分,凑不成就压栈。总分接着第一遍的 10 往上加。
- 20指针看残串第 0 位,是 "a"。栈顶是 空的。判一下能不能凑成 "ab":要栈顶是 "a"、当前是 "b"。
- 21凑不成 "ab",把 "a" 压进栈。总分还是 10。
- 22指针看残串第 1 位,是 "b"。栈顶是 "a"。判一下能不能凑成 "ab":要栈顶是 "a"、当前是 "b"。
- 23栈顶 "a" 配上当前 "b",凑成一个 "ab",消掉,加 4 分,总分变成 14。
- 24第二遍也扫完了。在残串 "ab" 上凑成了 1 个 "ab",每个 4 分,又进账 4 分。栈现在空了,再也凑不出任何一对。总分停在 14。
- 25回放一整局。从 "abbaab" 出发:第一遍贪心删掉 2 个高分对 "ba" 拿 10 分,残串 "ab";第二遍删掉 1 个低分对 "ab" 拿 4 分。10 加 4 等于 14,这就是最大得分。关键就在第一步定了「高分对先删」,顺序一对,分数自然到顶。
⚠️ 容易写错的地方
✗ 错：不分高低,随手先删便宜的那对
✓ 对：先比 x 和 y,分高的那对优先删满,再删另一对
"ab" 和 "ba" 抢的是同一批 a、b 字符,先删贵的能锁住高收益;反过来先删便宜的,可能把本该组成高分对的字符提前用掉,总分变小
✗ 错：担心两遍会互相破坏,想用一遍同时删两种
✓ 对：两遍各自独立:第一遍把高分对删光后剩下的残串,再删低分对不会回头影响已结算的分
高分对删光后,残串里不可能再生出新的高分对,所以两遍互不干扰,分数直接相加即可
✗ 错：栈法把空间复杂度报成 O(1)
✓ 对：两遍栈峰值是 O(n),只有计数法才是 O(1)
遇到像 "aaaa" 这种删不动的串,栈会把它们全摞住,占用随 n 增长,不能算常数
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int maximumGain(string s, int x, int y) {
char a = 'a', b = 'b';
if (x < y) {
swap(x, y);
swap(a, b);
}
int ans = 0, cnt1 = 0, cnt2 = 0;
for (char c : s) {
if (c == a) {
cnt1++;
} else if (c == b) {
if (cnt1) {
ans += x;
cnt1--;
} else {
cnt2++;
}
} else {
ans += min(cnt1, cnt2) * y;
cnt1 = 0;
cnt2 = 0;
}
}
ans += min(cnt1, cnt2) * y;
return ans;
}
};Java
import java.util.*;
class Solution {
public int maximumGain(String s, int x, int y) {
char a = 'a', b = 'b';
if (x < y) {
int t = x;
x = y;
y = t;
char c = a;
a = b;
b = c;
}
int ans = 0, cnt1 = 0, cnt2 = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
if (c == a) {
cnt1++;
} else if (c == b) {
if (cnt1 > 0) {
ans += x;
cnt1--;
} else {
cnt2++;
}
} else {
ans += Math.min(cnt1, cnt2) * y;
cnt1 = 0;
cnt2 = 0;
}
}
ans += Math.min(cnt1, cnt2) * y;
return ans;
}
}复杂度
时间
O(n)
n 是字符串长度。无论两遍栈还是一遍计数,每个字符只做常数次比较与加减,总共线性扫,合计 O(n)
空间
O(n) / O(1)
动画演示的两遍栈,栈最坏会摞住大半个串(比如全是 "aaaa"),峰值是 O(n);参考代码的计数法只用 cnt1、cnt2 两个整数,是 O(1)。看你用哪种实现。返回的总分不计入额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 删除子字符串的最大得分 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么证明高分对优先一定最优,而不是某些情况下先删低分对更好?+
关键看一对 "ab" 和一对 "ba" 什么时候会冲突。它们冲突,当且仅当共用了某个字符,比如串里一段 "aba",中间那个字符既能跟左边凑 "ab" 又能跟右边凑 "ba",你只能二选一。这时显然该选分高的那种。而互不冲突的对子,先删后删都能删到,顺序无所谓。把所有冲突点都判给高分对,总分就到顶了。所以贪心高分优先,既覆盖了冲突点的最优选择,又不影响非冲突点,整体最优。
能不能不开两遍栈,一遍扫完就出答案?+
可以,这正是参考代码的计数法。先交换保证 x 是高分值,然后一遍扫:用 cnt1 记还没配对的高分对首字符个数,遇到尾字符就立刻结算高分;低分对的字符先攒在 cnt2 里,等遇到一个无关字符或扫到结尾时,用两个计数的较小值乘低分值一次性结算。它把两遍栈压成一遍计数,空间从 O(n) 降到 O(1),思路本质还是高分优先。
这类题怎么认套路?+
特征是有几种局部消除操作、它们争抢同一批资源、每种操作有不同收益,问最大总收益。认出来后先排收益高低,贪心地优先满足高收益操作,再处理低收益的。能不能贪心,靠的就是证明「冲突点判给高收益方一定不亏」。栈在这里是删相邻可消对子的标准工具,凡是「删相邻满足某条件的一对」,都可以想到用栈。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 删除子字符串的最大得分 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。