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.
Solution:
class Solution {
public int beautySum(String s) {
int res = 0;
for (int len = 3; len <= s.length(); len ++) {
int[] count = new int[26];
for (int i = 0; i < s.length(); i ++) {
int in = s.charAt(i) - 'a';
count[in] ++;
if (i >= len) {
int out = s.charAt(i - len) - 'a';
count[out] --;
}
if (i >= len - 1) {
// System.out.println(Arrays.toString(count));
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int j = 0; j < 26; j ++) {
if (count[j] != 0) {
max = Math.max(max, count[j]);
min = Math.min(min, count[j]);
}
}
res += max - min;
}
}
}
return res;
}
}