题目描述
思路解析动画文字版
记牢这套动作:钉住左端、右端逐格往右扩、每加一个字符更新计数面板、用最高频减最低频得到这段的美丽值累加。下面每一帧都在套它,左端一个一个换,右端从左端一路扩到字符串末尾。
固定左端 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题