所有子字符串美丽值之和

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

难度中等

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

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

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

示例 1：

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

示例 2：

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

提示：

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

暴力求解（优化）

枚举所有子字符串，统计每个子字符串中的最大数量的字符的数量-最小数量的字符的数量的差值

class Solution {

    private int[]getHash(String s){
        int n=s.length();
        int count=0;
        int []hash=new int[26];
        for(int i=0;i<n;i++){
            if(hash[s.charAt(i)-'a']==0)count++;
            hash[s.charAt(i)-'a']++;
        }
        return hash;
    }
    private int getVal(int []hash){
        int max=0,min=Integer.MAX_VALUE;
        for(int i=0;i<26;i++){
            if(hash[i]!=0){
                if(hash[i]<min)min=hash[i];
                if(hash[i]>max)max=hash[i];
            }
        }

        return max-min;
    }
    public int beautySum(String s) {
        int n=s.length();
        int res=0;
        for(int i=0;i<n;i++){
            // 这里进行一次优化，从后往前遍历，这样的话可以减少hash数组统计的次数
            int []hash=getHash(s.substring(i,n));            
            for(int j=n-1;j>i;j--){
                res+=getVal(hash);
                // 每用完当前的字符，hash数组更新
                hash[s.charAt(j)-'a']--;
            }
        }
        return res;

    }
}

赏

谢谢你请我吃糖果

微信