所有子字符串美丽值之和 图解题解
这道题到底在问什么
- 输入
- s = "aabcb"
- 输出
- 5（美丽值非零的子串是 "aab" "aabc" "aabcb" "abcb" "bcb",各为 1）
- 输入
- 单看一段 "abaacc"
- 输出
- 美丽值 = 3 减 1 = 2（a 出现 3 次最多,b 出现 1 次最少）
先想最直接的笨办法
记牢这套动作:钉住左端、右端逐格往右扩、每加一个字符更新计数面板、用最高频减最低频得到这段的美丽值累加。下面每一帧都在套它,左端一个一个换,右端从左端一路扩到字符串末尾。（动画第 3 步）
最优解：一步一步想明白
- 3记牢这套动作:钉住左端、右端逐格往右扩、每加一个字符更新计数面板、用最高频减最低频得到这段的美丽值累加。下面每一帧都在套它,左端一个一个换,右端从左端一路扩到字符串末尾。
- 4换一个新的左端。把左指针钉在下标 0 的 "a" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 0 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
- 5右指针扩到下标 0,把 "a" 计进面板,现在 "a" 出现 1 次。当前子串是 "a",计数面板是 a×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 0。
- 6右指针扩到下标 1,把 "a" 计进面板,现在 "a" 出现 2 次。当前子串是 "aa",计数面板是 a×2。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 0。
- 7右指针扩到下标 2,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "aab",计数面板是 a×2, b×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 1。
- 8右指针扩到下标 3,把 "c" 计进面板,现在 "c" 出现 1 次。当前子串是 "aabc",计数面板是 a×2, b×1, c×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 2。
- 9右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 2 次。当前子串是 "aabcb",计数面板是 a×2, b×2, c×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 3。
- 10换一个新的左端。把左指针钉在下标 1 的 "a" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 1 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
- 11右指针扩到下标 1,把 "a" 计进面板,现在 "a" 出现 1 次。当前子串是 "a",计数面板是 a×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 3。
- 12右指针扩到下标 2,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "ab",计数面板是 a×1, b×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 3。
- 13右指针扩到下标 3,把 "c" 计进面板,现在 "c" 出现 1 次。当前子串是 "abc",计数面板是 a×1, b×1, c×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 3。
- 14右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 2 次。当前子串是 "abcb",计数面板是 a×1, b×2, c×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 4。
- 15换一个新的左端。把左指针钉在下标 2 的 "b" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 2 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
- 16右指针扩到下标 2,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "b",计数面板是 b×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 4。
- 17右指针扩到下标 3,把 "c" 计进面板,现在 "c" 出现 1 次。当前子串是 "bc",计数面板是 b×1, c×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 4。
- 18右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 2 次。当前子串是 "bcb",计数面板是 b×2, c×1。出现过的字符里最高频是 2 次、最低频是 1 次,美丽值就是 2 减 1 等于 1,把它累加进总和,现在总和 = 5。
- 19换一个新的左端。把左指针钉在下标 3 的 "c" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 3 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
- 20右指针扩到下标 3,把 "c" 计进面板,现在 "c" 出现 1 次。当前子串是 "c",计数面板是 c×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 5。
- 21右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "cb",计数面板是 c×1, b×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 5。
- 22换一个新的左端。把左指针钉在下标 4 的 "b" 上,计数面板先清空。接下来右指针会从这里一格一格往右挪,把每一个以下标 4 开头的子串都过一遍。现在面板还是空的,先看好起跑线。
- 23右指针扩到下标 4,把 "b" 计进面板,现在 "b" 出现 1 次。当前子串是 "b",计数面板是 b×1。出现过的字符次数都相等,最高频和最低频一样,这段美丽值是 0,总和不动,还是 5。
- 24五个左端都把右端扩到底了。回放一下:一共 15 个子串,美丽值不为 0 的正好是 "aab" "aabc" "aabcb" "abcb" "bcb" 这 5 段,每段都是 a 或 b 多一个、另一个字符少一个,最高频减最低频等于 1。其余子串要么全是同一个字符、要么每种字符都只出现一次,美丽值都是 0。把它们加起来,总和正好是 5。全程只做了计数加一、扫面板取最高最低、累加这三种小操作。
⚠️ 容易写错的地方
✗ 错：用定长 26 数组求最低频时,把计数为 0 的字母也算进去了
✓ 对：最低频只在「出现过的字符」里取,必须加「v 大于 0」的判断跳过 0
没在子串里出现的字母,它在数组里的计数是 0;如果把这些 0 也拿去比最小,最低频就永远是 0,美丽值会错等于最高频,整个答案偏大
✗ 错：内层右端每扩一格,都把当前子串的计数从头重新数一遍
✓ 对：右端每扩一格,只把新进来的那个字符计数加一,增量维护
新子串只比上一个子串在右边多一个字符,其它计数都没变;从头重建会多出一层和子串长度成正比的开销,总复杂度从 n 平方升到 n 的三次方
✗ 错：以为要把美丽值为 0 的子串挑出来跳过
✓ 对：全同字符、单字符这类子串美丽值本来就是 0,照常参与,只是加 0
题目求的是所有子串美丽值之和,加 0 不影响结果;特意去判断反而多此一举,真正贡献的是最高频和最低频拉开差距的那些子串
完整代码（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 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 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 beautySum(string s) {
int ans = 0;
int n = s.size();
int cnt[26];
for (int i = 0; i < n; ++i) {
memset(cnt, 0, sizeof cnt);
for (int j = i; j < n; ++j) {
++cnt[s[j] - 'a'];
int mi = 1000, mx = 0;
for (int& v : cnt) {
if (v > 0) {
mi = min(mi, v);
mx = max(mx, v);
}
}
ans += mx - mi;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int beautySum(String s) {
int ans = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
int[] cnt = new int[26];
for (int j = i; j < n; ++j) {
++cnt[s.charAt(j) - 'a'];
int mi = 1000, mx = 0;
for (int v : cnt) {
if (v > 0) {
mi = Math.min(mi, v);
mx = Math.max(mx, v);
}
}
ans += mx - mi;
}
}
return ans;
}
}复杂度
时间
O(n²·Σ)
n 是字符串长度,Σ 是字符集大小 26。外层左端 n 个,内层右端最多 n 个,合起来枚举了大约 n 平方个子串;每扩一格都要扫一遍 26 个计数取最高频和最低频,26 是常数。Python 用 Counter 求 max 和 min 是在出现过的字符上,最多也是 26 个,同阶
空间
O(Σ) = O(1)
计数结构最多装 26 个字母的计数,不随字符串变长而增加,峰值就是这 26 个格子,是常数级
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 所有子字符串美丽值之和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
右端每扩一格,为什么不用把子串的计数从头重建?+
因为新的子串只比上一个子串在右边多了一个字符,其它字符的计数都没变。所以只要把新字符的计数加一,就得到了新子串的完整计数,是常数时间的更新。要是每次都从左端重新数一遍,内层就多出一层和子串长度成正比的开销,总复杂度会从 n 平方升到 n 的三次方。增量维护是这类题的关键。
这道题还能不能做到比 O(n²) 更快?+
很难。答案是对全部子串求和,而长度 n 的字符串本身就有 n 乘 n 加 1 除以 2 个子串,数量级就是 n 平方,每一段都要贡献自己的美丽值。我们已经把每个子串的处理压到常数,只加一个字符再扫 26 个格子,所以 n 平方基本就是这类「对所有子串某个统计量求和」问题的下界了。
碰到「对所有子串维护某个统计量求和」的题,通用套路是什么?+
固定左端点,让右端点逐格往右扩,同时增量维护一个随右端移动而更新的状态。本题这个状态是 26 个字母的计数,别的题里可能是哈希、前缀异或值、或者某种单调结构。每扩一格就用当前状态算出这一段的贡献累加进答案。识别点是题目要「枚举所有连续子串,并且每段能算出一个可以增量维护的量」。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 所有子字符串美丽值之和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。