Sum of Beauty of All Substrings
The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.
- For example, the beauty of
"abaacc"is3 - 1 = 2.
Given a string s, return the sum of beauty of all of its substrings.
Example 1
Input
s = "aabcb"Output
5The substrings with non-zero beauty are ["aab", "aabc", "aabcb", "abcb", "bcb"], each with beauty equal to 1.
Example 2
Input
s = "aabcbaa"Output
17The sum of the beauty values over all substrings of
s is 17.Constraints
- 1 <= s.length <=^ 500
- s consists of only lowercase English letters.