LeetCode 1781. 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" 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 answer = 0;
        
        for (int i = 0; i < s.length(); i++) {
            int array[26] = {0};
            
            for (int j = i; j < s.length(); j++) {
                char ch = s[j];
                array[ch-'a']++;
                
                int maximum = INT_MIN;
                int minimum = INT_MAX;
                int diff_chars = 0;
                for (int k = 0; k < 26; k++) {
                    maximum = max(maximum, array[k]);
                    if (array[k] > 0) {
                        minimum = min(minimum, array[k]);
                        diff_chars++;
                    }
                }
                
                if (diff_chars >= 2) {
                    answer += (maximum - minimum);
                }
            }
        }
        
        return answer;
    }
};