找到最大开销的子字符串 图解题解
这道题到底在问什么
- 输入
- s="adaa", chars="d", vals=[-1000]
- 输出
- 2 (最大开销子串是 "aa",价值 1 加 1)
- 输入
- s="abc", chars="abc", vals=[-1,-1,-1]
- 输出
- 0 (每个字符价值都是 -1,不如干脆选空串)
先想最直接的笨办法
正式扫描前先立个底:一个字符都不选,空子串开销就是 0,所以当前段和 cur 从 0 开始,答案 ans 也从 0 开始。这也保证了不管后面价值多惨,答案最少也是 0,不会是负数。下面从第 0 个价值往右一个一个看。（动画第 5 步）
最优解：一步一步想明白
- 3记牢这套口诀:先把字符换成价值,再一遍扫,cur 加上新价值,正的就留着接着长,负的就归零重开,全程用 ans 记最大。下面每一帧都在套它,先看换算。
- 4规则:chars 里的取 vals,其余取字母序先把每个字符换成价值。这个例子里 chars 是 "cf",vals 是 [-4, -6],所以 c 被改成 -4、f 被改成 -6,其余字母都按字母序:a 是 1、b 是 2、d 是 4、e 是 5。把 s = "abcdefab" 一个个换过来,就得到下面这排价值 [1, 2, -4, 4, 5, -6, 1, 2]。接下来的活儿,就是在这排数里找一段连续的、和最大的子段。
- 5基线:cur = 0,ans = 0正式扫描前先立个底:一个字符都不选,空子串开销就是 0,所以当前段和 cur 从 0 开始,答案 ans 也从 0 开始。这也保证了不管后面价值多惨,答案最少也是 0,不会是负数。下面从第 0 个价值往右一个一个看。
- 6当前价值 1看第 0 个字符 "a",它的价值是 1(它不在 chars 里,按字母序算,a 是第 1 个字母)。此刻手里没有在生长的段,cur 是 0,这个字符很可能成为新一段的开头。
- 7cur = 1把价值 1 加到 cur 上,得到 1,还是正的,这一段值得留着,绿色往右扩到第 0 个。它比之前的最大开销还大,ans 刷新成 1,眼下最赚的子串是 "a"。
- 8当前价值 2看第 1 个字符 "b",它的价值是 2(它不在 chars 里,按字母序算,b 是第 2 个字母)。绿色是眼下正在生长的这一段,和是 1,马上把新价值加进去。
- 9cur = 3把价值 2 加到 cur 上,得到 3,还是正的,这一段值得留着,绿色往右扩到第 1 个。它比之前的最大开销还大,ans 刷新成 3,眼下最赚的子串是 "ab"。
- 10当前价值 -4看第 2 个字符 "c",它的价值是 -4(它在 chars 里,直接取 vals 给的 -4)。绿色是眼下正在生长的这一段,和是 3,马上把新价值加进去。
- 11cur 归零把价值 -4 加到 cur 上,3 加 -4 等于 -1,成了负数。这说明带着前面这段一起走反而亏,不如把它整个丢掉。cur 归零,红色这个 "c" 就是压垮这一段的那一下。段清空,等下一个字符另起一段。ans 还是 3,不受影响。
- 12当前价值 4看第 3 个字符 "d",它的价值是 4(它不在 chars 里,按字母序算,d 是第 4 个字母)。此刻手里没有在生长的段,cur 是 0,这个字符很可能成为新一段的开头。
- 13cur = 4把价值 4 加到 cur 上,得到 4,还是正的,这一段值得留着,绿色往右扩到第 3 个。它比之前的最大开销还大,ans 刷新成 4,眼下最赚的子串是 "d"。
- 14当前价值 5看第 4 个字符 "e",它的价值是 5(它不在 chars 里,按字母序算,e 是第 5 个字母)。绿色是眼下正在生长的这一段,和是 4,马上把新价值加进去。
- 15cur = 9把价值 5 加到 cur 上,得到 9,还是正的,这一段值得留着,绿色往右扩到第 4 个。它比之前的最大开销还大,ans 刷新成 9,眼下最赚的子串是 "de"。
- 16暂定赢家 "de"停一下看清楚:从第 3 个 d 到第 4 个 e 这一段,价值 4 加 5 等于 9,是目前为止最赚的子串。ans 就记着这个 9。往后还要接着扫,看有没有哪一段能翻过 9,如果没有,它就是最终答案。
- 17当前价值 -6看第 5 个字符 "f",它的价值是 -6(它在 chars 里,直接取 vals 给的 -6)。绿色是眼下正在生长的这一段,和是 9,马上把新价值加进去。
- 18cur = 3把价值 (-6) 加到 cur 上,得到 3,还是正的,这一段值得留着,绿色往右扩到第 5 个。不过它没超过已经见过的最大 9,ans 保持不变。
- 19cur 变小未归零这里要分清一件事:f 的价值是 -6,把 cur 从 9 削到了 3。cur 只是变小了,但还是大于等于 0,所以这一段并没有断,绿色继续留着往后走。只有当 cur 加完真的变成负数时才归零重开,单纯变小不算。同时 ans 早把 9 记下了,削到 3 也抢不走这个记录。
- 20当前价值 1看第 6 个字符 "a",它的价值是 1(它不在 chars 里,按字母序算,a 是第 1 个字母)。绿色是眼下正在生长的这一段,和是 3,马上把新价值加进去。
- 21cur = 4把价值 1 加到 cur 上,得到 4,还是正的,这一段值得留着,绿色往右扩到第 6 个。不过它没超过已经见过的最大 9,ans 保持不变。
- 22当前价值 2看第 7 个字符 "b",它的价值是 2(它不在 chars 里,按字母序算,b 是第 2 个字母)。绿色是眼下正在生长的这一段,和是 4,马上把新价值加进去。
- 23cur = 6把价值 2 加到 cur 上,得到 6,还是正的,这一段值得留着,绿色往右扩到第 7 个。不过它没超过已经见过的最大 9,ans 保持不变。
- 24答案 = 9八个价值全部扫完,ans 最终停在 9。回头看:ab 攒到过 3,被 c 清零;de 攒到 9 封了顶;f 把段削到 3 没能断掉它,收尾的 ab 也只回到 6,谁都没翻过 9。所以最大开销子字符串就是绿色这段 "de",答案 9。整道题就一条主线:字符换价值,再一遍 Kadane 找最大子段和。
⚠️ 容易写错的地方
✗ 错：忘了空子串,让答案可能是负数
✓ 对：ans 从 0 起,cur 加完变负就归零
题目允许一个字符都不选,空子串开销为 0,所以答案最少是 0;不设这条,全负的输入会返回负数
✗ 错：cur 只是变小就急着归零重开
✓ 对：只有 cur 加完 < 0 才归零
cur 变小但仍 ≥ 0 说明这段还划算,该继续留着;提前归零会漏掉后面本可接上的更大子段
✗ 错：不在 chars 里的字符忘了按字母序取值
✓ 对：默认价值是字母序 a=1..z=26
只有 chars 列出的字符才用 vals,其余一律按字母表位置,漏掉默认值会把价值算错
✗ 错：去枚举所有子串再求和取最大
✓ 对：一遍 Kadane 线性求解
枚举所有子串是 O(n 方) 甚至更高,数据一大就超时;Kadane 一遍扫就够
完整代码（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 maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
d = {c: v for c, v in zip(chars, vals)}
ans = tot = mi = 0
for c in s:
v = d.get(c, ord(c) - ord('a') + 1)
tot += v
ans = max(ans, tot - mi)
mi = min(mi, tot)
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 maximumCostSubstring(string s, string chars, vector<int>& vals) {
vector<int> d(26);
iota(d.begin(), d.end(), 1);
int m = chars.size();
for (int i = 0; i < m; ++i) {
d[chars[i] - 'a'] = vals[i];
}
int ans = 0, tot = 0, mi = 0;
for (char& c : s) {
int v = d[c - 'a'];
tot += v;
ans = max(ans, tot - mi);
mi = min(mi, tot);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maximumCostSubstring(String s, String chars, int[] vals) {
int[] d = new int[26];
for (int i = 0; i < d.length; ++i) {
d[i] = i + 1;
}
int m = chars.length();
for (int i = 0; i < m; ++i) {
d[chars.charAt(i) - 'a'] = vals[i];
}
int ans = 0, tot = 0, mi = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
int v = d[s.charAt(i) - 'a'];
tot += v;
ans = Math.max(ans, tot - mi);
mi = Math.min(mi, tot);
}
return ans;
}
}复杂度
时间
O(n)
n 是字符串 s 的长度。建价值映射只跟 chars 有关,chars 最多 26 个字符,是常数;之后把 s 从头到尾扫一遍,每个字符做几次常数运算,所以整体随 s 的长度线性增长
空间
O(1)
按峰值算。价值映射不管用字典还是数组,大小都被 26 个小写字母封顶,是常数;扫描时只用 cur、ans、mi 或 tot 这几个变量。都不随 s 变长而变大
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找到最大开销的子字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路一句话怎么说?+
先把字符串每个字符按规则换成价值,问题就变成经典的「最大子段和」,再用 Kadane 一遍扫:维护当前段和 cur,每来一个价值就 cur 取 max(0, cur 加价值),负了归零重开,同时用 ans 记录见过的最大 cur。因为空子串合法,ans 从 0 起,保证答案至少是 0。
参考代码里的 tot 减 mi 和 Kadane 是什么关系?+
完全等价。设 tot 是走到当前位置的前缀和,mi 是这之前见过的最小前缀和(含空前缀 0),那么「以当前位置结尾的最大子段和」就是 tot 减 mi。它和 Kadane 里的 cur 是同一个量,只是一个从前缀和的角度算、一个从递推的角度算,两种写法都是 O(n)。
为什么时间是线性,空间是常数?+
价值映射只跟 chars 有关,chars 最多 26 个字符,建表是常数;之后把 s 扫一遍,每个字符做几次常数运算,所以时间是 O(n)。空间上,价值表被 26 个字母封顶、扫描只用 cur、ans 这几个变量,都不随 s 变长而增大,所以是 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 找到最大开销的子字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。