Sum of Beauty of All Substrings: Frequency Counting Done Right
Solve Sum of Beauty of All Substrings with an incremental frequency count — intuition, JavaScript code, a worked walkthrough, and O(n²·26) complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
"Beauty" sounds like a trick word, but it hides a clean definition: the beauty of a string is its most frequent character count minus its least frequent character count. For "abaacc", a appears 3 times and c appears 2 — the rarest present letter, b, appears once — so beauty = 3 − 1 = 2.
This problem asks for the beauty of every contiguous substring, all summed together. That "every substring" phrasing scares people into thinking they need something clever. They don't. The real skill here is noticing that you can build each substring's frequency table incrementally instead of recounting from scratch — the same move that turns a lot of O(n³) string problems into O(n²).
The problem
Given a string s of lowercase English letters, compute the sum of the beauty of all of its contiguous substrings. The beauty of a substring is the maximum character frequency minus the minimum character frequency, where the minimum is taken over characters that actually appear (never zero).
Input: s = "aabcb"
Output: 5
Only these substrings have non-zero beauty:
"aab" -> a:2, b:1 -> 2 - 1 = 1
"aabc" -> a:2, b:1, c:1 -> 2 - 1 = 1
"aabcb" -> a:2, b:2, c:1 -> 2 - 1 = 1
"abcb" -> a:1, b:2, c:1 -> 2 - 1 = 1
"bcb" -> b:2, c:1 -> 2 - 1 = 1
Sum = 5Two constraints quietly define the solution:
- The alphabet is fixed at 26 lowercase letters, so a frequency "map" is really a size-26 array.
nis small (≤ 500 on LeetCode), which means an O(n²) enumeration of substrings is not just allowed — it's expected.
The brute force baseline
The literal reading generates every substring, then counts characters inside each one from scratch.
function beautySum(s) {
let total = 0;
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const freq = new Array(26).fill(0);
for (let k = i; k <= j; k++) { // recount every time
freq[s.charCodeAt(k) - 97]++;
}
let max = 0, min = Infinity;
for (const c of freq) if (c > 0) { max = Math.max(max, c); min = Math.min(min, c); }
total += max - min;
}
}
return total;
}There are about n²/2 substrings, and the innermost k loop re-scans up to n characters for each one. That's O(n³) work. The waste is obvious: the substring s[i..j] is just s[i..j-1] with one more character on the end, yet we throw away the count we already had and rebuild it letter by letter.
The key insight: extend, don't rebuild
Fix the left endpoint i. Now walk the right endpoint j from i outward. Each time j moves one step right, exactly one new character enters the substring. So instead of recounting, you just do freq[s[j]]++ — a single O(1) update — and the frequency table for s[i..j] is ready.
This is the substring-enumeration-with-running-state pattern: a fresh count per left endpoint, then an incremental extension for each right endpoint. It collapses the inner recount loop entirely, dropping the cost from O(n³) to O(n²) times whatever it takes to read max and min.
Reading max and min is cheap too: the array is always size 26, so scanning it is O(26) = O(1). The only subtlety is that the minimum must ignore zero entries — a letter that doesn't appear in this substring isn't the "rarest present" letter, it's simply absent.
The optimal solution
This mirrors the algorithm the visualizer steps through: an outer loop over the start index, a fresh 26-slot freq array per start, an inner loop that increments one slot and reads max/min over the non-zero entries.
function beautySum(s) {
let totalBeauty = 0;
for (let i = 0; i < s.length; i++) {
let freq = new Array(26).fill(0);
for (let j = i; j < s.length; j++) {
freq[s.charCodeAt(j) - 97]++;
let max = 0, min = Infinity;
for (let c of freq) {
if (c > 0) { max = Math.max(max, c); min = Math.min(min, c); }
}
totalBeauty += (max - min);
}
}
return totalBeauty;
}Two lines carry the whole idea. freq = new Array(26).fill(0) resets state whenever the left endpoint moves — substrings starting at i share no prefix with those starting at i-1, so the count can't carry over. And freq[s.charCodeAt(j) - 97]++ is the incremental extension: charCodeAt(j) - 97 maps 'a'→0 … 'z'→25, and the single ++ is all that separates s[i..j-1] from s[i..j].
Walkthrough
Tracing s = "aabcb" (indices a=0, a=1, b=2, c=3, b=4). freq resets at every new i; max/min scan only the non-zero slots.
| i | j | substring | freq (non-zero) | max | min | beauty | totalBeauty |
|---|---|---|---|---|---|---|---|
| 0 | 0 | "a" | a:1 | 1 | 1 | 0 | 0 |
| 0 | 1 | "aa" | a:2 | 2 | 2 | 0 | 0 |
| 0 | 2 | "aab" | a:2, b:1 | 2 | 1 | 1 | 1 |
| 0 | 3 | "aabc" | a:2, b:1, c:1 | 2 | 1 | 1 | 2 |
| 0 | 4 | "aabcb" | a:2, b:2, c:1 | 2 | 1 | 1 | 3 |
| 1 | 1 | "a" | a:1 | 1 | 1 | 0 | 3 |
| 1 | 2 | "ab" | a:1, b:1 | 1 | 1 | 0 | 3 |
| 1 | 3 | "abc" | a:1, b:1, c:1 | 1 | 1 | 0 | 3 |
| 1 | 4 | "abcb" | a:1, b:2, c:1 | 2 | 1 | 1 | 4 |
| 2 | 2 | "b" | b:1 | 1 | 1 | 0 | 4 |
| 2 | 3 | "bc" | b:1, c:1 | 1 | 1 | 0 | 4 |
| 2 | 4 | "bcb" | b:2, c:1 | 2 | 1 | 1 | 5 |
| 3 | 3 | "c" | c:1 | 1 | 1 | 0 | 5 |
| 3 | 4 | "cb" | c:1, b:1 | 1 | 1 | 0 | 5 |
| 4 | 4 | "b" | b:1 | 1 | 1 | 0 | 5 |
Every single-character substring has beauty 0 (max = min = 1), and so does any substring where all present letters tie. Beauty only appears once one letter pulls ahead — like the moment "aab" gives a a lead of 2 over b's 1. The running total lands on 5, matching the expected output.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (recount) | O(n³) | O(1) | ~n²/2 substrings × up to n chars recounted each |
| Incremental frequency | O(n²·26) | O(1) | n² substrings × a 26-slot max/min scan |
Because 26 is a constant, the incremental version is effectively O(n²) time and O(1) space — the freq array never grows past 26 slots regardless of input length. The outer O(n²) structure is unavoidable: the answer depends on every substring, and there are Θ(n²) of them to sum.
Common mistakes
- Recounting each substring. Rebuilding
freqfromitojinside the inner loop is the O(n³) trap. Increment one slot per step instead. - Forgetting to reset
freqwheniadvances. Substrings starting at a new left endpoint share no characters with the previous batch. Skip the reset and every count bleeds into the next start index. - Letting
mincount absent letters. If you take the minimum over all 26 slots, you'll always get 0 (from unused letters) and beauty collapses to justmax. Guard withif (c > 0)sominonly sees letters that appear. - Initializing
min = 0. Start it atInfinity; the first present letter should set the floor, not a stale zero. - Off-by-one on the substring range. The inner loop runs
jfromi(noti + 1), so single-character substrings are included — they contribute 0, but skipping them shifts every window.
Where this pattern shows up next
Enumerating substrings while carrying running state — a frequency array, a stack, a counter — is a workhorse across string problems:
- Minimum Add to Make Parentheses Valid — a single left-to-right pass carrying a running balance instead of a frequency table.
- Reverse Words in a String — scanning and rebuilding a string in one traversal.
- Decode String — a stack holding running state as you expand nested substrings.
- Count and Say — run-length frequency counting applied to a self-describing sequence.
You can also step through Sum of Beauty of All Substrings interactively to watch the frequency map grow one character at a time and see max, min, and the running total update per substring.
FAQ
What does "beauty" mean in this problem?
The beauty of a string is the frequency of its most common character minus the frequency of its least common character, counting only characters that actually appear. For "aabcb", the letter a and b each appear twice while c appears once, so beauty = 2 − 1 = 1. A string where every present character has the same count — like "abc" or "aa" — has beauty 0.
Why is the minimum taken only over characters that appear?
Because an absent letter isn't the "rarest" letter of the substring — it's not in the substring at all. If you naively scanned all 26 frequency slots, the unused letters would report a count of 0 and force the minimum to 0, making beauty equal to just the maximum. Restricting the minimum to non-zero counts (if (c > 0)) is what makes the definition correct.
What is the time and space complexity?
Time is O(n²·26), which simplifies to O(n²) since 26 is a constant. There are about n²/2 substrings, and each one costs a fixed 26-slot scan to read max and min. Space is O(1): the frequency array is always exactly 26 integers, no matter how long the input string is. The recount-from-scratch brute force is O(n³), which the incremental update avoids.
Can this be solved faster than O(n²)?
Not meaningfully, because the answer sums a value over Θ(n²) distinct substrings, so you have to touch each substring at least once. The incremental frequency update already makes the per-substring work constant, so O(n²) is the practical floor. With n ≤ 500 on LeetCode, that's about 125,000 substrings — fast enough that no further optimization is needed.
Why reset the frequency array for each start index?
Each iteration of the outer loop begins a new family of substrings that all start at index i, and these share no characters with the substrings that started at i − 1. Carrying the old counts forward would contaminate every window in the new batch with characters that aren't in them. Allocating a fresh new Array(26).fill(0) per start index keeps each batch's counts honest.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.