# 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;
    }
};
```
