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).
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; }}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.