Sum of Beauty of All Substrings
MedPrompt
The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.
- For example, the beauty of
"abaacc"is3 - 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 <= 500sconsists of only lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
totalBeauty = 0. - Iterate
ifrom0tos.length() - 1. - Iterate
jfromitos.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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Initialize
totalBeauty = 0. - Iterate
ifrom0tos.length() - 1(this will be the start of our substrings). - Initialize a frequency array
freqof size 26 to all zeros. - Iterate
jfromitos.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.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
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; }}/** * @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 ; };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 ansclass 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; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.