所有子字符串美丽值之和【LC1781】
The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.
For example, the beauty of "abaacc" is 3 - 1 = 2.
Given a string s, return the sum of beauty of all of its substrings.
开始居家的第一天
- 题意：统计所有子字符串的美丽值⌈ \lceil⌈同一字母的最大出现次数-最小出现次数⌋ \rfloor⌋之和
- 思路：双层循环暴力遍历每个子字符串s[i,j]，统计最大频率和最小频率
。最大频率取决于当前字母是否会影响最大频率，因此只需一个变量记录前一子字符串s[i,j−1]的最大频率即可
。最小频率则需要遍历哈希表统计最小频率，如果s[i,j−1]的最小频率为s[j]的对应的字母，那么当再次出现改字母时，可能的最小频率为其他任意字母
- 实现
class Solution { public int beautySum(String s) { int n = s.length(); int ans = 0; for (int i = 0; i < n ; i++){ int[] charToCount = new int[26]; int maxFreq = 0; for (int j = i; j < n; j++){ charToCount[s.charAt(j) - 'a']++; int minFreq = Integer.MAX_VALUE; maxFreq = Math.max(maxFreq,charToCount[s.charAt(j) - 'a']); for (int k = 0; k < 26; k++){ if (charToCount[k] > 0){ minFreq = Math.min(minFreq, charToCount[k]); } } ans += maxFreq - minFreq; } } return ans; } }
。复杂度
- 时间复杂度：O ( n 2 C )
- 空间复杂度：O ( 1 )
