LeetCode 1781. 所有子字符串美丽值之和 题解

示例

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

这题光用文字解说还是无法达到讲解题目的预期，所以就结合图文一并来讲讲本题，我的做题思路

如图所示是abaacc这串字符串的遍历过程，根据题目我们可以知道，只有当三个字符起步的时候，才可能存在差值并可以计入统计的子字符串，r向右扩展l每次都得从0开始向右扩展至r-2,遍历所有的子字符串然后统计差值计入sum

维护的话我就选择使用map来统计数目，然后通过Math.max和Math.min方法获取最大的值和最小的值

class Solution {public int beautySum(String s) {// 可暴力 右扩展左收缩int n = s.length();int ans = 0;for(int i=0;i<n;i++){int l = 0;while(l<=i-2){HashMap<Character,Integer> map = new HashMap<>();int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;char val2 = s.charAt(l);for(int j=l;j<=i;j++){char val = s.charAt(j);map.put(val,map.getOrDefault(val,0)+1);}for(Map.Entry<Character,Integer> entry:map.entrySet()){// System.out.println("key="+entry.getKey()+" value="+entry.getValue());max = Math.max(max,entry.getValue());min = Math.min(min,entry.getValue());}ans+=max-min;// System.out.println("ans:"+ans);map.put(val2,map.getOrDefault(val2,0)-1);l++;}}return ans;}
}

虽然跑样例的确是过了，且其复杂度也和官方题解描述的暴力方法差不多，但是由于使用了map维护导致复杂度还是会略高于使用数组维护，所以最后也是喜提了超时报红。

class Solution {public int beautySum(String s) {int res = 0;for (int i = 0; i < s.length(); i++) {int[] cnt = new int[26];int maxFreq = 0;for (int j = i; j < s.length(); j++) {cnt[s.charAt(j) - 'a']++;maxFreq = Math.max(maxFreq, cnt[s.charAt(j) - 'a']);int minFreq = s.length();for (int k = 0; k < 26; k++) {if (cnt[k] > 0) {minFreq = Math.min(minFreq, cnt[k]);}}res += maxFreq - minFreq;}}return res;}
}

这上面是官方题解，和我思路差不多，都是暴力求解