每日一题：12.12的LeetCode挑战题是哪一道？

本文共计551个文字，预计阅读时间需要3分钟。

1781. 子字符串美丽值定义如下：一个字符串的美丽值是出现频率最高的字符与出现频率最低的字符的出现次数之差。比例如，字符串abaacc的美丽值为3-1=2。

​​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; }};

官方：