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.

&nbsp;
Example 1:

Input: s = "aabcb"
Output: 5
Explanation: The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.

Example 2:

Input: s = "aabcbaa"
Output: 17


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 500
	s consists of only lowercase English letters.


class Solution:
    def beautySum(self, s: str) -> int:
        c, n, ans = Counter(s), len(s), 0
        for i in range(n-2):
            x=c.copy()
            for j in range(n-1,i+1,-1):
                ans+=max(x.values())-min(x.values())
                if x[s[j]]==1:
                    del x[s[j]]
                else:
                    x[s[j]]-=1
            if c[s[i]]==1:
                del c[s[i]]
            else:
                c[s[i]]-=1
        return ans
class Solution {
    private int getMinCount(int[] charCount) {
        int min = Integer.MAX_VALUE;
		
        for (int i = 0; i < charCount.length; ++i) {
            if (charCount[i] != 0) {
                min = Math.min(min, charCount[i]);
            }
        }
		
        return min;
    }
    
    private int getMaxCount(int[] charCount) {
        int max = 0;
		
        for (int i = 0; i < charCount.length; ++i) {
            max = Math.max(max, charCount[i]);
        }
		
        return max;
    }
    
    public int beautySum(String s) {
        int sum = 0;
        
        for (int i = 0; i < s.length(); ++i) {
            int[] charCount = new int[26]; // initialize charCount to all 0
            
            for (int j = i; j < s.length(); ++j) {
                ++charCount[s.charAt(j) - 'a'];

				// get beauty of substring from i to j
				int beauty = getMaxCount(charCount) - getMinCount(charCount);
                sum += beauty;
            }
        }
        
        return sum;
    }
}
class Solution {
public:
    int beautySum(string s) {
        int n = s.length(), sum = 0;
        for (int i = 0; i < n - 1; i++) {
            vector<int> dp(26, 0);
            dp[s[i] - 'a']++;
            for (int j = i + 1; j < n; j++) {
                dp[s[j] - 'a']++;
                int minNum = INT_MAX, maxNum = INT_MIN;
                for (int k = 0; k < 26; k++) {
                    if (dp[k]) minNum = min(minNum, dp[k]);
                    if (dp[k]) maxNum = max(maxNum, dp[k]);
                }
                sum = sum + (maxNum - minNum);
            }
        }
        return sum;
    }
};
var beautySum = function(s) {
    const len = s.length;

    let ans = 0;
    const freq = new Array(26).fill(0);

    for(let i = 0; i < len; i++) {
        freq[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        for(let j = i + 1; j < len; j++) {
            freq[s[j].charCodeAt(0) - 'a'.charCodeAt(0)]++;
            ans += minMaxDiff(freq);
        }
        freq.fill(0);
    }

    function minMaxDiff(freq) {
        freq = freq.filter(f => f != 0);
        return Math.max(...freq) - Math.min(...freq);
    }

    return ans;
};
Sum of Beauty of All Substrings