Sum of Beauty of All Substrings

The beauty of a string is defined as beauty = (frequency of the most frequent character) − (frequency of the least frequent character) counting only…

The **beauty** of a string is defined as beauty = (frequency of the most frequent character) − (frequency of the least frequent character) counting only characters that **actually appear** in the string. For example, the beauty of `"aabcb"` is `2 − 1 = 1` (`a` appears twice, `c` once). Given a lowercase string `s`, return the **sum of the beauty of every substring** of `s`. A substring is a contiguous run of characters. Indexing is **0-based**. Recomputing the frequency table for each of the O(n²) substrings is wasteful. Instead, fix a start index `i` and extend the end index `j` one character at a time, keeping a single 26-slot frequency array updated in O(1). For the current substring `s[i..j]`, scan the 26 slots for the largest and smallest non-zero frequency; their difference is that substring's beauty. Summing the beauty over all `(i, j)` pairs gives the answer in O(n² · 26) time and O(26) space. **Example:** `s = "xyx"`. Only the substring `"xyx"` is beautiful (`x:2, y:1` → beauty 1); every other substring has all characters at equal frequency, so the total is `1`.

- `1 <= s.length <= 500` - `s` consists only of lowercase English letters.

Example 1: input s = "aabcb"; output 5. The beautiful substrings "aab", "aabc", "aabcb", "abcb", "bcb" each have beauty 1; the rest have beauty 0.

Example 2: input s = "xyx"; output 1. Only "xyx" has non-zero beauty (x:2, y:1 → 2 − 1 = 1).

Example 3: input s = "zzzz"; output 0. Every substring has a single distinct character, so its max and min frequencies are equal — beauty is always 0.

Category: Strings. Topic: strings. Difficulty: Medium. Patterns: hashing.