LeetCode 题解工作台
所有子字符串美丽值之和
一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。 比方说， "abaacc" 的美丽值为 3 - 1 = 2 。 给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。 示例 1： 输入： s = "aabcb" 输出： 5 解释： 美丽值不为零的字符串包括 …
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 哈希·表·结合·string
答案摘要
枚举每个子串的起点位置 ，找到以该起点位置的字符为左端点的所有子串，然后计算每个子串的美丽值，累加到答案中。 时间复杂度 $O(n^2 \times C)$，空间复杂度 。其中 为字符串的长度，而 为字符集的大小。本题中 $C = 26$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。
- 比方说，
"abaacc"的美丽值为3 - 1 = 2。
给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。
示例 1：
输入：s = "aabcb" 输出：5 解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。
示例 2：
输入：s = "aabcbaa" 输出：17
提示：
1 <= s.length <= 500s只包含小写英文字母。
解题思路
方法一：枚举 + 计数
枚举每个子串的起点位置 ，找到以该起点位置的字符为左端点的所有子串，然后计算每个子串的美丽值，累加到答案中。
时间复杂度 ，空间复杂度 。其中 为字符串的长度，而 为字符集的大小。本题中 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidate correctly calculates substring character frequencies.
- question_mark
Listen for mention of optimizing repeated frequency counts with prefix sums.
- question_mark
Watch for understanding of beauty computation as max-min frequency difference.
常见陷阱
外企场景- error
Forgetting to ignore zero-frequency characters when computing minimum frequency.
- error
Recounting character frequencies for each substring without optimization.
- error
Assuming beauty is always non-zero for single-character substrings.
进阶变体
外企场景- arrow_right_alt
Calculate sum of squared beauties instead of simple differences.
- arrow_right_alt
Only consider substrings of a fixed length k.
- arrow_right_alt
Return the maximum beauty of any substring instead of the total sum.