# Sum of Beauty of All Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-beauty-of-all-substrings)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-beauty-of-all-substrings
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Fastenal](https://scaleengineer.com/companies/fastenal)
---
## Problem
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.

# Approaches
## Brute-Force by Generating All Substrings
This approach involves generating every possible substring of the input string `s`. For each of these substrings, we calculate its beauty and add it to a running total. The beauty is found by first counting character frequencies within the substring and then finding the difference between the maximum and minimum frequency.
**Time:** `O(N^3)`, where `N` is the length of the string. There are `O(N^2)` substrings. For each substring of length `L`, calculating its beauty takes `O(L)` time. The sum of lengths of all substrings is `O(N^3)`. · **Space:** `O(1)` or `O(26)` because the frequency map used for calculating beauty has a constant size.
**Pros:** Simple to understand and implement.; Directly follows the problem definition.
**Cons:** Highly inefficient due to redundant calculations. The frequency map for each substring is computed from scratch.; Likely to result in a 'Time Limit Exceeded' (TLE) error for larger inputs (like `N=500`).
### Explanation
The algorithm uses three nested loops. The outer two loops (with indices `i` and `j`) are used to define the start and end points of all possible substrings. For each substring `sub = s.substring(i, j + 1)`, a helper function is used to compute its beauty.

To compute the beauty of `sub`, we first create a frequency map (an array of size 26 for lowercase English letters). We iterate through `sub` to populate this frequency map. Then, we iterate through the frequency map to find the highest frequency (`maxFreq`) and the lowest non-zero frequency (`minFreq`). The beauty of `sub` is `maxFreq - minFreq`. This beauty value is added to a total sum. After iterating through all substrings, the total sum is returned.

```java
class Solution {
    public int beautySum(String s) {
        int totalBeauty = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                totalBeauty += calculateBeauty(sub);
            }
        }
        return totalBeauty;
    }

    private int calculateBeauty(String sub) {
        if (sub.length() < 2) {
            return 0;
        }
        int[] freq = new int[26];
        for (char c : sub.toCharArray()) {
            freq[c - 'a']++;
        }

        int maxFreq = 0;
        int minFreq = Integer.MAX_VALUE;
        for (int count : freq) {
            if (count > 0) {
                maxFreq = Math.max(maxFreq, count);
                minFreq = Math.min(minFreq, count);
            }
        }
        return maxFreq - minFreq;
    }
}
```
### Algorithm
* Initialize `totalBeauty = 0`.
* Iterate `i` from `0` to `s.length() - 1`.
*   Iterate `j` from `i` to `s.length() - 1`.
*     Extract the substring `sub = s.substring(i, j + 1)`.
*     Create a frequency array `freq` of size 26, initialized to zeros.
*     For each character `c` in `sub`, increment `freq[c - 'a']`.
*     Find `maxFreq` and `minFreq` from the `freq` array (ignoring zero counts).
*     Calculate `beauty = maxFreq - minFreq`.
*     Add `beauty` to `totalBeauty`.
* Return `totalBeauty`.

## Optimized Double Loop Approach
This approach improves upon the brute-force method by avoiding redundant calculations. Instead of generating each substring and then calculating its frequencies, we fix the starting point of the substrings and extend the end point one character at a time. We maintain a running frequency count for the current substring, updating it as we extend the substring.
**Time:** `O(N^2)`. The two nested loops run `O(N^2)` times. Inside the inner loop, we update the frequency map (`O(1)`) and then iterate through the 26-element map to find min/max frequencies (`O(26)` or `O(1)`). Thus, the total time is `O(N^2 * 26)`, which simplifies to `O(N^2)`. · **Space:** `O(1)` or `O(26)`. We only need a constant-size array to store frequencies for the current set of substrings starting at `i`.
**Pros:** Much more efficient than the `O(N^3)` approach.; Efficient enough to pass the given constraints (`N <= 500`).; Still relatively easy to understand.
**Cons:** This is the optimal solution for the given constraints, so there are no significant cons in this context.
### Explanation
The algorithm uses two nested loops. The outer loop with index `i` fixes the starting character of the substrings. The inner loop with index `j` iterates from `i` to the end of the string, extending the substring one character at a time.

A frequency map (an array of size 26) is initialized for each starting position `i`. As the inner loop progresses (from `j = i` to `n-1`), we consider the substring `s.substring(i, j+1)`. We update the frequency of the character `s.charAt(j)` in our map. After each update, we calculate the beauty of the current substring `s.substring(i, j+1)` using the updated frequency map.

To find the beauty, we iterate through the 26-element frequency map to find the maximum and minimum non-zero frequencies. This beauty is added to the total sum. This way, for a fixed start `i`, we calculate the beauty of all substrings starting at `i` in a single pass of the inner loop.

```java
class Solution {
    public int beautySum(String s) {
        int totalBeauty = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                
                int maxFreq = 0;
                int minFreq = Integer.MAX_VALUE;
                
                for (int k = 0; k < 26; k++) {
                    if (freq[k] > 0) {
                        maxFreq = Math.max(maxFreq, freq[k]);
                        minFreq = Math.min(minFreq, freq[k]);
                    }
                }
                totalBeauty += (maxFreq - minFreq);
            }
        }
        return totalBeauty;
    }
}
```
### Algorithm
* Initialize `totalBeauty = 0`.
* Iterate `i` from `0` to `s.length() - 1` (this will be the start of our substrings).
*   Initialize a frequency array `freq` of size 26 to all zeros.
*   Iterate `j` from `i` to `s.length() - 1` (this will be the end of our substrings).
*     Increment the frequency of the character `s.charAt(j)` in `freq`.
*     Find `maxFreq` and `minFreq` from the `freq` array (ignoring zero counts).
*     Calculate `beauty = maxFreq - minFreq`.
*     Add `beauty` to `totalBeauty`.
* Return `totalBeauty`.

# Solutions
### Java

```java
class Solution {
public
  int beautySum(String s) {
    int ans = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      int[] cnt = new int[26];
      for (int j = i; j < n; ++j) {
        ++cnt[s.charAt(j) - 'a'];
        int mi = 1000, mx = 0;
        for (int v : cnt) {
          if (v > 0) {
            mi = Math.min(mi, v);
            mx = Math.max(mx, v);
          }
        }
        ans += mx - mi;
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {number} */ var beautySum = function ( s ) { let ans = 0 ; for ( let i = 0 ; i < s . length ; ++ i ) { const cnt = new Map (); for ( let j = i ; j < s . length ; ++ j ) { cnt . set ( s [ j ], ( cnt . get ( s [ j ]) || 0 ) + 1 ); const t = Array . from ( cnt . values ()); ans += Math . max (... t ) - Math . min (... t ); } } return ans ; };
```

### Python

```python
class Solution:
    def beautySum(self, s: str) -> int: ans, n = 0, len(s) for i in range(n): cnt = Counter() for j in range(i, n): cnt[s[j]] += 1 ans += max(cnt . values()) - min(cnt . values()) return ans

```

### CPP

```cpp
class Solution {
public:
  int beautySum(string s) {
    int ans = 0;
    int n = s.size();
    int cnt[26];
    for (int i = 0; i < n; ++i) {
      memset(cnt, 0, sizeof cnt);
      for (int j = i; j < n; ++j) {
        ++cnt[s[j] - 'a'];
        int mi = 1000, mx = 0;
        for (int &v : cnt) {
          if (v > 0) {
            mi = min(mi, v);
            mx = max(mx, v);
          }
        }
        ans += mx - mi;
      }
    }
    return ans;
  }
};

```