题目描述
思路解析
一句话答案：LeetCode 1781 所有子字符串美丽值之和：枚举每个左端、右端逐格右扩，边扩边维护 26 个字母的计数，每步用最高频减最低频累加，省掉从头重数。时间 O(n²·26)、空间 O(1)。
美丽值到底怎么算，这题要把哪些子串的美丽值相加
先说美丽值怎么来。一个字符串的美丽值，是它里面出现次数最多的字符的次数，减去出现次数最少、但至少出现过一次的字符的次数。题目给你字符串 s，要求把 s 的每一个连续子字符串的美丽值都算出来，再全部加起来。拿题面 s='aabcb' 来说，答案是 5；再看一段 'abaacc'，里面 a 出现 3 次最多、b 出现 1 次最少，它的美丽值就是 3 减 1 等于 2。
把每个子串都重新数一遍字符，代价高在哪
长度 n 的字符串，连续子串大约有 n²/2 个，这个数量绕不过去——答案就是要对每一个子串各算一次美丽值。真正贵的是每段的处理：如果对着一个子串，从它的左端到右端把字符重新数一遍，再取最高频和最低频，单个子串就要花和它长度成正比的时间，全部加起来是 O(n³)。字符串稍微一长，这层重复计数就把时间拖垮了。
右端每多接一个字符，为什么计数只需要动一格
相邻两个子串只差最右边那一个字符。把左端钉住不动，右端每往右挪一格，新的子串只比上一个子串在右边多出一个字符，前面那些字符的计数一个都没变。于是不必从头重数，只要把新进来的这个字符的计数加一，就得到了新子串的完整计数——这种每步只改动新增那一格、别的照旧的做法叫增量维护。每扩一格后，在当前计数里取最高频减最低频，就是这一段的美丽值。要留意最低频只在真正出现过的字符里取，计数还是 0 的字母不能算进来。
固定左端、右端逐格扩，整个流程怎么跑
外层从下标 0 开始，依次让每个位置当一次子串的左端；每换一个新左端，就把计数清空。内层让右端从当前左端出发，一格一格扩到字符串末尾，每扩到一个字符就把它的计数加一，再取当前计数里的最高频减最低频，累加进答案。左端走遍所有位置，所有子串就都被覆盖了一遍，累加出来的就是总美丽值。
aabcb 里哪几段子串真有美丽值
左端钉在下标 0：子串 'a'、'aa' 里字符次数都相等，美丽值都是 0；扩到 'aab' 时 a 两次、b 一次，2 减 1 得 1；'aabc'、'aabcb' 里仍是最高 2、最低 1，各得 1，这一轮共加 3。左端挪到下标 1：'a'、'ab'、'abc' 全是 0，'abcb' 里 b 两次、a 和 c 各一次，得 1。左端到下标 2：'b'、'bc' 是 0，'bcb' 得 1。左端在下标 3、4 起头的 'c'、'cb'、'b' 都是 0。有贡献的正好是 'aab' 'aabc' 'aabcb' 'abcb' 'bcb' 五段，加起来是 5。
求最低频，先跳过计数为 0 的字母
这套做法时间是 O(n²·26)、空间 O(1)，计数最多占 26 个格子。有几处容易出错。用定长 26 的数组存计数时，那些没在子串里出现的字母还挂着 0，求最低频要跳过这些 0，只在计数大于 0 的字母里取最小；忘了跳过，最低频永远是 0，美丽值就错等于最高频，总和整个偏大。右端扩格必须增量加一，图省事从头重数会把复杂度推回 O(n³)。还有单字符、以及整段同一个字符的子串，它们的美丽值本来就是 0，照常参与累加即可，加 0 不影响结果，特意挑出来跳过反而多此一举。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套动作:钉住左端、右端逐格往右扩、每加一个字符更新计数面板、用最高频减最低频得到这段的美丽值累加。下面每一帧都在套它,左端一个一个换,右端从左端一路扩到字符串末尾。
固定左端 0 · 出发：换一个新的左端。把左指针钉在下标 0 的 "a" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 0 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
左端 0 · 右端扩到 0：右指针扩到下标 0,把 "a" 计进面板,现在 "a" 出现 1 次。当前子串是 "a",计数面板是 a×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 0。
左端 0 · 右端扩到 1：右指针扩到下标 1,把 "a" 计进面板,现在 "a" 出现 2 次。当前子串是 "aa",计数面板是 a×2。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 0。
左端 0 · 右端扩到 2：右指针扩到下标 2,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "aab",计数面板是 a×2, b×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 1。
左端 0 · 右端扩到 3：右指针扩到下标 3,把 "c" 计进面板,现在 "c" 出现 1 次。当前子串是 "aabc",计数面板是 a×2, b×1, c×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 2。
左端 0 · 右端扩到 4：右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 2 次。当前子串是 "aabcb",计数面板是 a×2, b×2, c×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 3。
固定左端 1 · 出发：换一个新的左端。把左指针钉在下标 1 的 "a" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 1 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
左端 1 · 右端扩到 1：右指针扩到下标 1,把 "a" 计进面板,现在 "a" 出现 1 次。当前子串是 "a",计数面板是 a×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 3。
左端 1 · 右端扩到 2：右指针扩到下标 2,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "ab",计数面板是 a×1, b×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 3。
左端 1 · 右端扩到 3：右指针扩到下标 3,把 "c" 计进面板,现在 "c" 出现 1 次。当前子串是 "abc",计数面板是 a×1, b×1, c×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 3。
左端 1 · 右端扩到 4：右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 2 次。当前子串是 "abcb",计数面板是 a×1, b×2, c×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 4。
固定左端 2 · 出发：换一个新的左端。把左指针钉在下标 2 的 "b" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 2 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
左端 2 · 右端扩到 2：右指针扩到下标 2,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "b",计数面板是 b×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 4。
左端 2 · 右端扩到 3：右指针扩到下标 3,把 "c" 计进面板,现在 "c" 出现 1 次。当前子串是 "bc",计数面板是 b×1, c×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 4。
左端 2 · 右端扩到 4：右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 2 次。当前子串是 "bcb",计数面板是 b×2, c×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 5。
固定左端 3 · 出发：换一个新的左端。把左指针钉在下标 3 的 "c" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 3 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
左端 3 · 右端扩到 3：右指针扩到下标 3,把 "c" 计进面板,现在 "c" 出现 1 次。当前子串是 "c",计数面板是 c×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 5。
左端 3 · 右端扩到 4：右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "cb",计数面板是 c×1, b×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 5。
固定左端 4 · 出发：换一个新的左端。把左指针钉在下标 4 的 "b" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 4 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
左端 4 · 右端扩到 4：右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "b",计数面板是 b×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 5。
完成 · 答案 5：五个左端都把右端扩到底了。回放一下:一共 15 个子串,美丽值不为 0 的正好是 "aab" "aabc" "aabcb" "abcb" "bcb" 这 5 段,每段都是 a 或 b 多一个、另一个字符少一个,最高频减最低频等于 1。其余子串要么全是同一个字符、要么每种字符都只出现一次,美丽值都是 0。把它们加起来,总和正好是 5。全程只做了计数加一、扫面板取最高最低、累加这三种小操作。
边界先想清:单字符美丽值 0;整串同一个字符时所有子串都是 0;像 "aab" 只有最长那段拉开了频差贡献 1,其余全 0。
面试重点:右端扩格增量维护计数(避免升到 n 的三次方);子串总数就是 n 平方级、这类求和题很难更快;通用套路是固定左端、右端扩、增量维护随右端更新的状态。
参考代码
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 beautySum(self, s: str) -> int: ans, n = 0, len(s) for i in range(n): cnt = Counter() for j in range(i, n): cnt[s[j]] += 1 ans += max(cnt.values()) - min(cnt.values()) return ans复杂度
- 时间：O(n²·Σ)，n 是字符串长度,Σ 是字符集大小 26。外层左端 n 个,内层右端最多 n 个,合起来枚举了大约 n 平方个子串;每扩一格都要扫一遍 26 个计数取最高频和最低频,26 是常数。Python 用 Counter 求 max 和 min 是在出现过的字符上,最多也是 26 个,同阶
- 空间：O(Σ) = O(1)，计数结构最多装 26 个字母的计数,不随字符串变长而增加,峰值就是这 26 个格子,是常数级
易错点
面试追问把动画讲成自己的话
追问右端每扩一格,为什么不用把子串的计数从头重建?
追问这道题还能不能做到比 O(n²) 更快?
追问碰到「对所有子串维护某个统计量求和」的题,通用套路是什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
替换字符串中的括号内容
LeetCode 1807 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题