Sum Frequency Imbalance Across Substrings

### Problem For a nonempty string, define its beauty as its largest character frequency minus its smallest positive character frequency. For lowercase string `s`, sum this quantity over every contiguous nonempty substring and return the total. ```cpp class Solution { public: int beautySum(string s); }; ``` ### Examples **Example 1:** ```text s = "aaab" Output: 3 Explanation: Only aab and aaab have nonzero beauty, respectively 1 and 2. ``` **Example 2:** ```text s = "abab" Output: 2 Explanation: The substrings aba and bab each contribute 1; every other substring contributes 0. ``` ### Constraints - `1 <= s.length <= 500`. - Characters are lowercase English letters. ### Clarifying Questions The least frequent character must occur in that substring. Absent alphabet letters are excluded, as the source examples establish. ```hint Inspect the structure Which character frequencies are eligible for the minimum in one substring's beauty? ``` ### Reasoning checkpoints - Account for every eligible substring occurrence without omission or duplication. - Compute the minimum only among positive frequencies. ### Optional extensions How would prefix character counts compare with incrementally extending every left endpoint?