LC 1781. 所有子字符串美丽值之和

题目描述

这是 LeetCode 上的 1781. 所有子字符串美丽值之和 ，难度为 中等。

一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

比方说，"abaacc" 的美丽值为 3 - 1 = 2。

给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。

示例 1：

1
2
3
4
5
输入：s = "aabcb"

输出：5

解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。

示例 2：
1
2
3
输入：s = "aabcbaa"

输出：17

提示：

  • $1 <= s.length <= 500$
  • s 只包含小写英文字母。

模拟 + 哈希表

数据范围只有 $500$，我们可以通过两层循环的方式枚举所有子串，当枚举子串左端点 i 的时候，可以同步开一个大小为 $C = 26$ 的数组来记录每个字母的出现次数，随后通过遍历该数组来得知最大和最小频次，将当前子串对应的美丽值累加到答案。

该做法复杂度为 $O(n^2 \times C)$，计算量约为 $500 \times 500 \times 26 = 6.5 \times 10^6$，可以过。

在确定了子串的左端点 i，枚举右端点 j 的过程中，维护最大频次是简单的，关键在于如果知晓最小频次，我们可以额外起一个哈希表 map 来记录出现频次为 x 的字符有多少个，map[x] = cnt 含义为频次为 x 的字符类型有 cnt 种。

假设当前我们处理的字符为 c，根据字符 c 原来的频次进行分情况讨论（使用 max 和 min 分别记录当前最大最小频次）：

  • 若字符 c 为首次出现，即原频次为 $0$，此时有最小频次 min = 1
  • 当字符 c 为并非首次出现，假设原频次数为 x，此时频次为 x 的字符数量减一；频次为 x + 1 的字符数量加一，若频次为 x 的字符数量在减一后 $map[min] \leq 0$，说明没有频次为 min 的字符了，此时最小频次为 min + 1

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int beautySum(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i++) {
            int[] cnts = new int[26];
            Map<Integer, Integer> map = new HashMap<>();
            int min = -1, max = -1;
            for (int j = i; j < n; j++) {
                int c = s.charAt(j) - 'a';
                map.put(cnts[c], map.getOrDefault(cnts[c], 0) - 1);
                map.put(cnts[c] + 1, map.getOrDefault(cnts[c] + 1, 0) + 1);
                cnts[c]++;
                if (cnts[c] == 1) min = 1;
                else if (map.get(min) <= 0) min++;
                max = Math.max(max, cnts[c]);
                ans += max - min;
            }
        }
        return ans;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public: 
    int beautySum(string s) {
        int n = s.size(), cnts[26], ans = 0;
        unordered_map<int, int> map;
        for(int i = 0; i < n; ++i) {
            memset(cnts, 0, sizeof(cnts));
            map.clear();
            int min = -1, maxv = -1;
            for(int j = i; j < n; ++j) {
                int c = s[j] - 'a';
                map[cnts[c]]--; map[cnts[c] + 1]++;
                cnts[c]++;
                if(cnts[c] == 1) min = 1;    
                else if(map[min] <= 0) min++;
                maxv = max(maxv, cnts[c]);
                ans += maxv - min;
            }
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def beautySum(self, s: str) -> int:
        n, ans = len(s), 0
        for i in range(n):
            cnts = [0] * 26
            dmap = defaultdict(int)
            maxv, minv = -1, -1
            for j in range(i, n):
                c = ord(s[j]) - ord('a')
                dmap[cnts[c]] -= 1
                dmap[cnts[c] + 1] += 1
                cnts[c] += 1
                if cnts[c] == 1:
                    minv = 1
                elif dmap[minv] <= 0:
                    minv += 1
                maxv = max(maxv, cnts[c])
                ans += maxv - minv
        return ans

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function beautySum(s: string): number {
    let n = s.length, ans = 0
    for (let i = 0; i < n; i++) {
        const cnts = new Array<number>(26).fill(0)
        const map = new Map()
        let min = 0, max = 0
        for (let j = i; j < n; j++) {
            const c = s.charCodeAt(j) - 'a'.charCodeAt(0)
            if (!map.has(cnts[c])) map.set(cnts[c], 0)
            map.set(cnts[c], map.get(cnts[c]) - 1)
            if (!map.has(cnts[c] + 1)) map.set(cnts[c] + 1, 0)
            map.set(cnts[c] + 1, map.get(cnts[c] + 1) + 1)
            cnts[c]++
            if (cnts[c] == 1) min = 1
            else if (map.get(min) <= 0) min++
            max = Math.max(max, cnts[c])
            ans += max - min
        }
    }
    return ans
}

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(C)$，其中 $C = 26$ 为字符集大小

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1781 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。