题目描述
思路解析动画文字版
记牢这套口诀:先把字符换成价值,再一遍扫,cur 加上新价值,正的就留着接着长,负的就归零重开,全程用 ans 记最大。下面每一帧都在套它,先看换算。
第一步 · 把 8 个字符换成价值：先把每个字符换成价值。这个例子里 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]。接下来的活儿,就是在这排数里找一段连续的、和最大的子段。
第二步 · 一遍扫描开始：正式扫描前先立个底:一个字符都不选,空子串开销就是 0,所以当前段和 cur 从 0 开始,答案 ans 也从 0 开始。这也保证了不管后面价值多惨,答案最少也是 0,不会是负数。下面从第 0 个价值往右一个一个看。
看第 0 个 · 字符 "a" 价值 1：看第 0 个字符 "a",它的价值是 1(它不在 chars 里,按字母序算,a 是第 1 个字母)。此刻手里没有在生长的段,cur 是 0,这个字符很可能成为新一段的开头。
结算第 0 个 · 段和 = 1,刷新最大：把价值 1 加到 cur 上,得到 1,还是正的,这一段值得留着,绿色往右扩到第 0 个。它比之前的最大开销还大,ans 刷新成 1,眼下最赚的子串是 "a"。
看第 1 个 · 字符 "b" 价值 2：看第 1 个字符 "b",它的价值是 2(它不在 chars 里,按字母序算,b 是第 2 个字母)。绿色是眼下正在生长的这一段,和是 1,马上把新价值加进去。
结算第 1 个 · 段和 = 3,刷新最大：把价值 2 加到 cur 上,得到 3,还是正的,这一段值得留着,绿色往右扩到第 1 个。它比之前的最大开销还大,ans 刷新成 3,眼下最赚的子串是 "ab"。
看第 2 个 · 字符 "c" 价值 -4：看第 2 个字符 "c",它的价值是 -4(它在 chars 里,直接取 vals 给的 -4)。绿色是眼下正在生长的这一段,和是 3,马上把新价值加进去。
结算第 2 个 · 段和变负,归零重开：把价值 -4 加到 cur 上,3 加 -4 等于 -1,成了负数。这说明带着前面这段一起走反而亏,不如把它整个丢掉。cur 归零,红色这个 "c" 就是压垮这一段的那一下。段清空,等下一个字符另起一段。ans 还是 3,不受影响。
看第 3 个 · 字符 "d" 价值 4：看第 3 个字符 "d",它的价值是 4(它不在 chars 里,按字母序算,d 是第 4 个字母)。此刻手里没有在生长的段,cur 是 0,这个字符很可能成为新一段的开头。
结算第 3 个 · 段和 = 4,刷新最大：把价值 4 加到 cur 上,得到 4,还是正的,这一段值得留着,绿色往右扩到第 3 个。它比之前的最大开销还大,ans 刷新成 4,眼下最赚的子串是 "d"。
看第 4 个 · 字符 "e" 价值 5：看第 4 个字符 "e",它的价值是 5(它不在 chars 里,按字母序算,e 是第 5 个字母)。绿色是眼下正在生长的这一段,和是 4,马上把新价值加进去。
结算第 4 个 · 段和 = 9,刷新最大：把价值 5 加到 cur 上,得到 9,还是正的,这一段值得留着,绿色往右扩到第 4 个。它比之前的最大开销还大,ans 刷新成 9,眼下最赚的子串是 "de"。
定格 · 目前最赚的子串是 "de"：停一下看清楚:从第 3 个 d 到第 4 个 e 这一段,价值 4 加 5 等于 9,是目前为止最赚的子串。ans 就记着这个 9。往后还要接着扫,看有没有哪一段能翻过 9,如果没有,它就是最终答案。
看第 5 个 · 字符 "f" 价值 -6：看第 5 个字符 "f",它的价值是 -6(它在 chars 里,直接取 vals 给的 -6)。绿色是眼下正在生长的这一段,和是 9,马上把新价值加进去。
结算第 5 个 · 段和 = 3：把价值 (-6) 加到 cur 上,得到 3,还是正的,这一段值得留着,绿色往右扩到第 5 个。不过它没超过已经见过的最大 9,ans 保持不变。
留意 · cur 变小但没变负,段不断：这里要分清一件事:f 的价值是 -6,把 cur 从 9 削到了 3。cur 只是变小了,但还是大于等于 0,所以这一段并没有断,绿色继续留着往后走。只有当 cur 加完真的变成负数时才归零重开,单纯变小不算。同时 ans 早把 9 记下了,削到 3 也抢不走这个记录。
看第 6 个 · 字符 "a" 价值 1：看第 6 个字符 "a",它的价值是 1(它不在 chars 里,按字母序算,a 是第 1 个字母)。绿色是眼下正在生长的这一段,和是 3,马上把新价值加进去。
结算第 6 个 · 段和 = 4：把价值 1 加到 cur 上,得到 4,还是正的,这一段值得留着,绿色往右扩到第 6 个。不过它没超过已经见过的最大 9,ans 保持不变。
看第 7 个 · 字符 "b" 价值 2：看第 7 个字符 "b",它的价值是 2(它不在 chars 里,按字母序算,b 是第 2 个字母)。绿色是眼下正在生长的这一段,和是 4,马上把新价值加进去。
结算第 7 个 · 段和 = 6：把价值 2 加到 cur 上,得到 6,还是正的,这一段值得留着,绿色往右扩到第 7 个。不过它没超过已经见过的最大 9,ans 保持不变。
答案 · 最大开销 = 9：八个价值全部扫完,ans 最终停在 9。回头看:ab 攒到过 3,被 c 清零;de 攒到 9 封了顶;f 把段削到 3 没能断掉它,收尾的 ab 也只回到 6,谁都没翻过 9。所以最大开销子字符串就是绿色这段 "de",答案 9。整道题就一条主线:字符换价值,再一遍 Kadane 找最大子段和。
边界想清:全负时空子串保底 0、非 chars 字符按字母序、负价值的尾巴不要硬带上。
面试重点:字符换价值加 Kadane、tot 减 mi 与 cur 等价、时间 O(n) 空间 O(1)。
参考代码
from __future__ import annotationsfrom 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 ans复杂度
- 时间：O(n)，n 是字符串 s 的长度。建价值映射只跟 chars 有关,chars 最多 26 个字符,是常数;之后把 s 从头到尾扫一遍,每个字符做几次常数运算,所以整体随 s 的长度线性增长
- 空间：O(1)，按峰值算。价值映射不管用字典还是数组,大小都被 26 个小写字母封顶,是常数;扫描时只用 cur、ans、mi 或 tot 这几个变量。都不随 s 变长而变大
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问参考代码里的 tot 减 mi 和 Kadane 是什么关系?
追问为什么时间是线性,空间是常数?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符串中的额外字符
LeetCode 2707 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题