1781. Sum of Beauty of All Substrings

Medium

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.

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:

• 1 <= s.length <= 500

• s consists of only lowercase English letters.

解題

func beautySum(s string) int {
    res := 0

    for i := 0; i < len(s); i++ {
        m := make(map[byte]int)
        for j := i; j < len(s); j++ {
            m[s[j]]++

            min, max := math.MaxInt32, math.MinInt32
            for _, v := range m {
                if v < min {
                    min = v
                }
                if v > max {
                    max = v
                }
            }
            res += max - min
        }
    }
    return res
}