[leetcode每日一题]12.12

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

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

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

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

示例 1：

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

示例 2：

输入：s = "aabcbaa"输出：17

提示：

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

Solution

前缀和，但是在第二天才做出来。实在是遗憾。

其实就是维护一下状态即可。两层循环，并记录出现次数。注意边界处理。

优化：由于长度大于2的子字符串才可能有贡献，所以在里层循环可以写+3。

我的方法其实还不够简洁。官方的写法更好。

代码(C++)

class Solution {public: int beautySum(string s) { int n = s.size(); vector<vector<int>> dic(26, vector<int>(n+1, 0)); for(int i=0;i<n;i++){ for(int j=0;j<26;j++){ dic[j][i+1] = dic[j][i]; } dic[s[i]-'a'][i+1] += 1; } // for(int i=0;i<=n;i++){ // for(int j=0;j<26;j++){ // cout<<dic[j][i]<<" "; // } // cout<<endl; // } int maxn; int minn; int res = 0; for(int i=0;i<n+1;i++){ for(int j=i+3;j<n+1;j++){ maxn = 0; minn = 501; for(int k=0;k<26;k++){ int tmp = (dic[k][j]-dic[k][i]); if(tmp){ maxn = max(maxn, tmp); minn = min(minn, tmp); } } // cout<<i<<" "<<j<<" "<<maxn<<" "<<minn<<endl; res += maxn - minn; } } return res; }};

官方：