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

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