难度: Medium
一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。
"abaacc" 的美丽值为 3 - 1 = 2 。给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。
示例 1：
输入：s = "aabcb" 输出：5 解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。
示例 2：
输入：s = "aabcbaa" 输出：17
提示：
1 <= s.length <= 500s 只包含小写英文字母。运行时间: 1043 ms
内存: 16.1 MB
class Solution:
def beautySum(self, s: str) -> int:
l = len(s)
cnt = 0
for i in range(l):
h = {}
maxVal, minVal = 0, 0
for j in range(i, l):
if s[j] not in h: h[s[j]] = 0
h[s[j]] += 1
maxVal = max(maxVal, h[s[j]])
minVal = min(h.values())
cnt += maxVal - minVal
return cnt
该题解使用了一个嵌套循环的方法，外层循环遍历字符串s的所有可能的起始位置i，内层循环遍历从位置i开始的所有可能的结束位置j。对于每个子字符串s[i:j+1]，使用一个哈希表h来记录每个字符的出现次数。同时，记录并更新当前子字符串中出现最频繁的字符的出现次数maxVal和出现最少的字符的出现次数minVal。每次内循环计算出一个新的子字符串时，都会更新哈希表，并重新计算maxVal和minVal，然后计算当前子字符串的美丽值（maxVal - minVal），并将其累加到总计数cnt中。最终返回总计数cnt作为所有子字符串的美丽值之和。
时间复杂度: O(n^2 * k)
空间复杂度: O(1)
class Solution:
def beautySum(self, s: str) -> int:
l = len(s)
cnt = 0
for i in range(l):
h = {}
maxVal, minVal = 0, 0
for j in range(i, l):
if s[j] not in h: h[s[j]] = 0 # 若字符未在哈希表中，则初始化为0
h[s[j]] += 1 # 更新字符出现频率
maxVal = max(maxVal, h[s[j]]) # 更新最高频率
minVal = min(h.values()) # 查找最低频率
cnt += maxVal - minVal # 计算并累加当前子字符串的美丽值
return cnt # 返回所有子字符串的美丽值之和
在每次内循环结束时重新计算最低频率minVal而不是在每次更新后立即进行，这样做主要是为了效率考虑。如果每增加一个字符就重新计算最低频率，那么每次更新字符频率后都需要遍历整个哈希表来寻找最小值，这会增加算法的时间复杂度。通过在每次内循环结束时重新计算，可以减少频繁的最小值搜索操作，从而提高效率。然而，这种方式仍然会导致在每次内循环结束时进行一次全哈希表的遍历，这在字符种类多的情况下依然是一个较大的计算负担。
在该算法中，哈希表h用于记录每个字符的出现频率。对于每个新出现的字符，如果字符不在哈希表中，算法会将其初始化为0并立即将其频率设置为1。如果字符已存在于哈希表中，则直接增加其计数。这种策略确保了每个字符的频率都能被准确记录与更新，便于算法在任何时刻都能获取到任何字符的当前频率。
在算法的每次外循环开始时，maxVal和minVal都被初始化。maxVal初始化为0，因为在开始探索新的子字符串时，任何字符的出现频率都不会超过0。minVal的初始值也设为0，这在逻辑上可能看起来有些不符合实际情况，因为最小频率应当是至少1或更高。然而，在实际计算过程中，minVal会在遇到第一个字符后立即更新，因此初始值在实际使用中会被快速覆盖。
该算法在效率上确实存在问题，尤其是在处理大字符串和字符种类多的情况下。每次添加一个新字符时重新计算最小频率需要遍历整个哈希表，这使得算法的时间复杂度较高。一种更高效的方式是使用优先队列（或其他数据结构，如有序列表）来维护字符频率的排序。这样，每次字符频率更新时，可以更快地调整排序并直接访问最小和最大频率值。这虽然增加了额外的数据结构管理开销，但可以显著减少每次查找最小和最大频率的时间，从而提高总体效率。