C++ LeetCode1781题解所有子字符串美丽值之和
目录
- LeetCode 1781.所有子字符串美丽值之和
- 方法一:前缀和
- AC代码
- C++
- 方法二:边遍历边计算
- AC代码
- C++
LeetCode 1781.所有子字符串美丽值之和
力扣题目链接:leetcode.cn/problems/su…
一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差。
- 比方说,
"abaacc"
的美丽值为3 - 1 = 2
。
给你一个字符串 s
,请你返回它所有子字符串的 美丽值 之和。
示例 1:
输入:s = "aabcb"
输出:5
解释:美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ,每一个字符串的美丽值都为 1 。
示例 2:
输入:s = "aabcbaa"
输出:17
提示:
1 <= s.length <= 500
s
只包含小写英文字母。
方法一:前缀和
我们分别统计出26种字母的前缀和
这样,我们只需要枚举子串区间(两重循环枚举子串首尾),再统计出这个区间中,字母的最大和最小出现频率,累加到答案中即可。
AC代码
C++
class Solution { public: int beautySum(string s) { int n = s.size(); vector<vector<int>> prefix(26, vector<int>(n + 1)); for (int i = 1; i <= n; i++) { for (int c = 0; c < 26; c++) { prefix[c][i] = prefix[c][i - 1]; } prefix[s[i - 1] - 'a'][i]++; } int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int M = 0, m = 1000; for (int c = 0; c < 26; c++) { int thisC = prefix[c][j + 1] - prefix[c][i]; M = max(M, thisC); if (thisC) { // 不能出现0次 m = min(m, thisC); } } // printf("i = %d, j = %d, M = %d, m = %d\n", i, j, M, m); //*********** ans += M - m; } } return ans; } };
方法二:边遍历边计算
方法一中,我们预处理使用前缀和计算出了每种元素的出现情况。但是每种字母的前缀和都需要O(len(s))O(len(s))O(len(s))的空间复杂度来保存
方法二中,我们不提前预处理计算出字母的出现情况,而是在枚举字符串终点的同时计算。这样,空间复杂度就减小了一个维度。
AC代码
C++
class Solution { public: int beautySum(string s) { int ans = 0; int n = s.size(); for (int i = 0; i < n; i++) { int cnt[26] = {0}; // 只需要开辟O(C)的空间 for (int j = i; j < n; j++) { cnt[s[j] - 'a']++; // 枚举子串终点的同时统计元素出现的次数 int M = 0, m = 1000; for (int d = 0; d < 26; d++) { M = max(M, cnt[d]); if (cnt[d]) m = min(m, cnt[d]); } ans += M - m; } } return ans; } };
以上就是C++ LeetCode1781题解所有子字符串美丽值之和的详细内容,更多关于C++ 子字符串美丽值和的资料请关注我们其它相关文章!
赞 (0)