AlgoViz
HomeStrings

Sum of Beauty of All Substrings

Medium

Extend each start, updating counts incrementally

Problem

The beauty of a string is (max char frequency - min nonzero char frequency). Return the sum of beauty over all substrings.

In simple words

For every substring, beauty is the gap between the most and least frequent letter counts; sum them.

The idea

Fix a start index and extend the end one character at a time, maintaining a frequency array as you go. Recomputing beauty from a 26-slot array is O(26) per substring, so the whole thing is O(n²·26) rather than O(n³).

The trick

  • Reuse the frequency array across the inner loop instead of rebuilding it.
  • Beauty = max count minus the smallest non-zero count.
  • Skip zero counts when finding the minimum.
a
a
b
c
b
0
1
2
3
4

Step 1 of 17. Brute force: for every substring, add (most − least frequent letter count). Values: a, a, b, c, b.

1/17
Brute force
timeO(n²)spaceO(1)

Every substring.

1for (let i = 0; i < n; i++) {2  const freq = {};3  for (let j = i; j < n; j++) { freq[s[j]]++; total += max(freq) - min(freq); }4}

Input

array
[a, a, b, c, b]

Output

total
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "aabcb"
Output:
5
Explanation:
Sum of (most - least frequent) over all substrings → 5.

Example 2

Input:
s = "aabcbaa"
Output:
17
Explanation:
Adds up to 17.

Example 3

Input:
s = "ab"
Output:
0
Explanation:
Single-letter substrings have beauty 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.