Sum of Beauty of All Substrings — Problem & Solution
Sum of Beauty of All Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum of Beauty of All Substrings is a medium coding problem on strings, hash table and counting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The beauty of a string is the difference between the number of times its most frequent character appears and the number of times its least frequent character appears — counting only characters that do appear.
For example, the beauty of "abaacc" is 3 - 1 = 2 (a appears three times, b once).
Given a string s, return the sum of the beauty of all of its substrings.
Example 1
Input: s = "kaaik"
Output: 5
Explanation: `"kaa"`, `"kaai"`, `"kaaik"`, `"aai"` and `"aaik"` each have beauty 1; every other substring has beauty 0.
Example 2
Input: s = "abcab"
Output: 3
Explanation: `"abca"`, `"bcab"` and `"abcab"` have beauty 1.
Example 3
Input: s = "zz"
Output: 0
Constraints
1 <= s.length <= 500s consists of only lowercase English letters
Hints for Sum of Beauty of All Substrings
Hint 1
There are about
n^2 / 2substrings — withn <= 500you can afford to look at every one, but not to recount each from scratch.Hint 2
Fix the start
iand extend the endjone character at a time, updating a 26-entry count array.Hint 3
After each extension, the beauty is the max count minus the smallest non-zero count — a 26-step scan.
How to solve Sum of Beauty of All Substrings
Enumerate substrings by start and end, maintaining character counts incrementally so each substring costs only a scan of the 26 counters.
Approach
- For each start
i, reset a 26-entry count array. - For each end
j >= i, increment the count ofs[j]. - Scan the counts: the largest value minus the smallest non-zero value is this substring's beauty; add it to the total.
Why it works
Every substring is s[i..j] for exactly one pair i <= j, and the count array after processing j holds exactly the frequencies of s[i..j].
Complexity
- Time —
O(26 · n^2) - Space —
O(26)
Pitfalls
- The minimum ignores letters with count 0 — otherwise every substring missing a letter would look beautiful.
- Recounting each substring from scratch is
O(n^3).
Reference solution
Python
def beautySum(s: str) -> int:
total = 0
n = len(s)
codes = [ord(c) - 97 for c in s]
for i in range(n):
cnt = [0] * 26
for j in range(i, n):
cnt[codes[j]] += 1
total += max(cnt) - min(v for v in cnt if v)
return totalJava
public static int beautySum(String s) {
int n = s.length(), total = 0;
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 mx = 0, mn = Integer.MAX_VALUE;
for (int v : cnt) {
if (v == 0) continue;
mx = Math.max(mx, v);
mn = Math.min(mn, v);
}
total += mx - mn;
}
}
return total;
}C++
int beautySum(string s) {
int n = s.size(), total = 0;
for (int i = 0; i < n; i++) {
int cnt[26] = {0};
for (int j = i; j < n; j++) {
cnt[s[j] - 'a']++;
int mx = 0, mn = INT_MAX;
for (int v : cnt) {
if (v == 0) continue;
mx = max(mx, v);
mn = min(mn, v);
}
total += mx - mn;
}
}
return total;
}JavaScript
var beautySum = function(s) {
var total = 0, n = s.length;
for (var i = 0; i < n; i++) {
var cnt = new Array(26).fill(0);
for (var j = i; j < n; j++) {
cnt[s.charCodeAt(j) - 97]++;
var mx = 0, mn = n + 1;
for (var c = 0; c < 26; c++) {
if (cnt[c] === 0) continue;
if (cnt[c] > mx) mx = cnt[c];
if (cnt[c] < mn) mn = cnt[c];
}
total += mx - mn;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets