STEP 5 · STRINGS · INCREMENTAL FREQUENCY TABLE · MEDIUM

Sum of Beauty of All Substrings

WHAT IT SAYS

The beauty of a string is its highest character frequency minus its lowest non-zero one. Sum the beauty of every substring.

WHAT IT'S REALLY ASKING

"You genuinely do have to visit all n^2 substrings — the answer is a sum over them, so there is no skipping. But the substrings that share a starting index form a chain where each one is the previous one plus a single character. And a frequency table only changes by one slot when you append a character. So why would you ever build the table twice?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Build a fresh count table per substring

O(n^3) time, O(1) space

For every start i and every end j, walk the characters from i to j, tallying them into a fresh 26-slot array, then take the max minus the min-over-present.

WHERE THE WORK IS WASTED — The table for s[i..j+1] differs from the table for s[i..j] in exactly ONE slot — the character you just appended. Yet the inner loop discards the table it already had and recounts the substring from its first character. A substring of length 500 gets its characters counted 500 times over the life of its chain, and 499 of those tallies were sitting in memory a moment before you deleted them.

KEY OBSERVATION — THE UNLOCKlink

Growing a substring by one letter is one increment.

Fix a starting index i. The substrings that begin there form a strictly nested chain: s[i..i], then s[i..i+1], then s[i..i+2], and so on. Each one is the previous one plus exactly one character on the right. That is not a coincidence about this problem — it is the shape of the substring space itself. Now ask what a frequency table does under that operation. Appending a character increments one slot and touches nothing else. A count table is purely additive; it has no memory of order and no interaction between slots. So the table for the next substring in the chain is ONE increment away from the one you are holding. Rebuilding it means throwing away a table you already own in order to reconstruct a table that differs from it in a single cell. Carry it instead, and the entire inner loop becomes one increment plus one evaluation. What about the evaluation? Max minus min needs a scan of the alphabet — but the alphabet is 26, a CONSTANT fixed by the problem statement, not by the input. So that scan is O(1) by definition. Say the 26 out loud, because it is the whole reason this is acceptable: the algorithm is O(26 * n^2), and the 26 is a constant that a Unicode version would not have. One trap, and it is a silent one. The minimum must be taken over characters that actually APPEAR — count greater than zero — not over all 26 slots. Include the absent characters and every minimum is 0, every beauty collapses to the maximum frequency, and your code runs perfectly while computing the wrong quantity.

One table per start, one increment per end

O(26 * n^2) time, O(26) space

For each start i, zero a 26-slot array. Extend j from i to the end of the string, incrementing exactly one slot each step. After each increment, scan the 26 slots for the largest count and the smallest non-zero count, and add their difference to the running answer.

WHAT YOU TRADED — You accept a quadratic algorithm because the answer is a sum over a quadratic number of substrings — you must touch each one at least once, so there is no better complexity class available. What you optimised is the CONSTANT: from re-scanning each substring to a single increment. That is an underrated move in its own right. If the alphabet were not a small constant, the 26-slot scan would become a hidden factor of k, and you would have to maintain counts-of-counts to keep max and min available in O(1).

WATCH THE IDEA RUN

a 0

b 0

c 0

beauty here 0

running total 0

Every substring must be visited — the answer is a sum over all of them. The only question is what each visit costs.

step 1 / 29

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Extend, Don't Rebuild

YOU'LL SEE IT AGAIN WHEN

You must evaluate every substring or subarray, and consecutive candidates in the natural enumeration differ by exactly one element.
The per-candidate summary is additive — a count table, a sum, a XOR, a running max — so it can be updated in O(1) instead of recomputed from scratch.
The value range or alphabet is a small fixed constant, which is what makes a 'scan the whole table' step O(1) rather than a hidden factor of n.

SAME BLUEPRINT, DIFFERENT PROBLEM

Longest Substring Without Repeating CharactersFind All Anagrams in a StringCount Substrings With K Distinct CharactersNumber of Substrings Containing All Three Characters

The bar isn't "solved it once." It's "could rebuild it from the observation."