1781. Sum of Beauty of All Substrings

Difficulty:
Related Topics:
Similar Questions:

Problem

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.

Given a string s, return **the sum of *beauty* of all of its substrings.**

  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

  Constraints:

Solution (Java)

class Solution {
    public int beautySum(String s) {
        int beauty = 0;
        for (int i = 0; i < s.length(); i++) {
            int[] numCountOfFreq = new int[s.length() + 1 - i];
            int[] charFreq = new int[26];
            charFreq[s.charAt(i) - 'a'] = 1;
            numCountOfFreq[1] = 1;
            int min = 1;
            int max = 1;
            for (int j = i + 1; j < s.length(); j++) {
                char c = s.charAt(j);
                charFreq[c - 'a']++;
                int freq = charFreq[c - 'a'];
                numCountOfFreq[freq - 1]--;
                numCountOfFreq[freq]++;
                if (numCountOfFreq[min] == 0) {
                    min++;
                }
                if (min > freq) {
                    min = freq;
                }
                if (max < freq) {
                    max = freq;
                }
                beauty += max - min;
            }
        }
        return beauty;
    }
}

Explain:

nope.

Complexity: