The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.
"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 <= 500s consists of only lowercase English letters.Problem Overview: You receive a string s. For every substring, compute its beauty, defined as the difference between the highest character frequency and the lowest non‑zero frequency in that substring. The goal is to sum this beauty value across all possible substrings.
Approach 1: Brute Force Frequency Recalculation (O(n^3) time, O(1) space)
The most direct method enumerates every substring using two indices i and j. For each substring s[i..j], rebuild a frequency array for the 26 lowercase characters, then compute the maximum and minimum non‑zero counts. The beauty value (maxFreq - minFreq) is added to the total. Because you recompute character counts for each substring, the inner operation scans the substring again, producing roughly O(n^3) time. Space stays O(1) since the alphabet size is constant. This approach is simple but inefficient for larger strings.
Approach 2: Optimized Expansion with Running Frequency (O(n^2) time, O(1) space)
A better approach fixes the starting index i and expands the substring one character at a time. Maintain a frequency array of size 26 while extending j. Each step updates the count of s[j], then recomputes the current maximum and minimum non‑zero frequencies by scanning the 26-element array. Since the alphabet is fixed, this scan is constant time. The substring frequencies are reused instead of rebuilt, reducing complexity to O(n^2). This technique relies on efficient character counting using a small array or hash table, combined with incremental substring growth from the string.
Approach 3: Prefix Frequency Precomputation (O(n^2) time, O(26n) space)
You can also build prefix frequency arrays where prefix[i][c] stores how many times character c appears up to index i. For any substring s[l..r], compute each character’s frequency using prefix[r] - prefix[l-1]. After retrieving counts, determine the max and min non‑zero frequencies to calculate the beauty. This avoids maintaining a mutable array while iterating but still requires scanning all 26 characters per substring. The complexity remains O(n^2), with extra memory for prefix storage. It’s a clean approach when working heavily with counting queries across ranges.
Recommended for interviews: The incremental frequency expansion approach is the expected solution. It demonstrates understanding of substring enumeration while avoiding redundant recomputation. Interviewers usually accept O(n^2) because the alphabet is fixed and scanning 26 characters is effectively constant time. Showing the brute force method first proves you understand the definition of beauty, then optimizing with running counts shows practical problem‑solving skill.
This approach involves generating all possible substrings of the input string and calculating the beauty of each substring. The beauty is determined by the frequency difference between the most common and least common character within the substring.
Although straightforward, this approach may be inefficient for larger strings due to the high number of substrings.
The function beauty_sum iterates over all possible substrings of s. For each substring, it maintains a frequency dictionary that is updated as characters are added to the substring. The calc_beauty function computes the beauty of the current substring using the max and min frequencies. The accumulated beauty is the result.
Time complexity: O(n^3), where n is the length of the string, as it involves generating all substrings and calculating frequencies.
Space complexity: O(1) - as the frequency dictionary size is bounded by the constant number of lowercase letters.
This approach reduces repetitive work in calculating frequencies by utilizing prefix frequency arrays that allow efficient substring frequency calculations. For each possible starting point of a substring, update and compute the necessary frequency values from earlier calculations.
This optimized Python solution uses a list of prefix frequency counters. Each counter at index i represents the frequency of characters from the start of the string up to but not including index i. Frequency differences within substrings are obtained using these prefix frequencies. This allows frequency calculation in constant time for each substring.
Time complexity: O(n^2), where n is the length of the string, as it reduces redundant frequency calculations.
Space complexity: O(n), due to storage of prefix frequency data.
Enumerate the starting position i of each substring, find all substrings with the character at this starting position as the left endpoint, then calculate the beauty value of each substring, and accumulate it to the answer.
The time complexity is O(n^2 times C), and the space complexity is O(C). Here, n is the length of the string, and C is the size of the character set. In this problem, C = 26.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: O(n^3), where n is the length of the string, as it involves generating all substrings and calculating frequencies. Space complexity: O(1) - as the frequency dictionary size is bounded by the constant number of lowercase letters. |
| Optimized Approach Using Prefix Frequency | Time complexity: O(n^2), where n is the length of the string, as it reduces redundant frequency calculations. Space complexity: O(n), due to storage of prefix frequency data. |
| Enumeration + Counting | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Frequency Recalculation | O(n^3) | O(1) | Useful for understanding the definition of beauty or during early problem exploration |
| Incremental Frequency Expansion | O(n^2) | O(1) | Best practical solution for interviews and competitive programming |
| Prefix Frequency Arrays | O(n^2) | O(26n) | Helpful when multiple substring frequency queries are required |
7. Sum of Beauty of All Substrings | Strings - Medium | Leetcode 1781 | Learn DSA • Ayushi Sharma • 26,213 views views
Watch 9 more video solutions →Practice Sum of Beauty of All Substrings with our built-in code editor and test cases.
Practice on FleetCode