#1781

Medium

LeetCode Problem Workspace

Sum of Beauty of All Substrings

Calculate the total beauty of all substrings by counting character frequencies and computing frequency differences efficiently.

hash table string counting

Problem Statement

Given a string s, define the beauty of a substring as the difference between the highest frequency and lowest frequency of characters within that substring. Compute the total sum of beauties for all possible substrings of s.

For example, with s = "aabcb", the substrings with non-zero beauty include ["aab","aabc","aabcb","abcb","bcb"]. Each substring's beauty is calculated based on character frequency differences, and the total sum across all substrings is returned. Constraints: 1 <= s.length <= 500, and s consists of only lowercase English letters.

Examples

Example 1

Input: s = "aabcb"

Output: 5

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

Example details omitted.

Constraints

1 <= s.length <= 500
s consists of only lowercase English letters.

Solution Approach

Brute Force with Frequency Counting

Iterate over all possible substrings, and for each substring, count character occurrences using a hash table. Compute the beauty as the difference between maximum and minimum non-zero frequencies and sum all beauties. This approach is simple but can be slow for longer strings due to O(n^3) time complexity.

Optimize with Prefix Frequency Arrays

Maintain a prefix sum array for character frequencies to avoid recounting each substring from scratch. For any substring, compute character counts by subtracting prefix values. This reduces repeated computation and aligns with the Hash Table plus String pattern, improving efficiency closer to O(n^2 * 26).

Early Exit for Uniform or Single Character Substrings

For substrings where all characters are the same, the beauty is zero. Detect these quickly to skip unnecessary calculations. This minor optimization prevents redundant hash table operations and reduces overall runtime, especially in strings with long runs of identical characters.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The naive approach requires O(n^3) time for all substrings and O(n) space for counting frequencies. Using prefix frequency arrays reduces time to O(n^2 * 26) with O(n*26) space, trading some memory for faster substring evaluation.

What Interviewers Usually Probe

Check if candidate correctly calculates substring character frequencies.
Listen for mention of optimizing repeated frequency counts with prefix sums.
Watch for understanding of beauty computation as max-min frequency difference.

Common Pitfalls or Variants

Common pitfalls

Forgetting to ignore zero-frequency characters when computing minimum frequency.
Recounting character frequencies for each substring without optimization.
Assuming beauty is always non-zero for single-character substrings.

Follow-up variants

Calculate sum of squared beauties instead of simple differences.
Only consider substrings of a fixed length k.
Return the maximum beauty of any substring instead of the total sum.

FAQ

What is the definition of beauty in the Sum of Beauty of All Substrings problem?

Beauty is defined as the difference between the highest and lowest non-zero character frequencies in a substring.

How can prefix frequency arrays optimize computing substring beauty?

By storing cumulative character counts, prefix arrays allow computing counts for any substring in O(26) time instead of recounting each character.

Does a substring with all identical characters contribute to the sum of beauty?

No, substrings with all identical characters have beauty zero and can be skipped in accumulation.

What pattern does this problem follow?

This problem follows the Hash Table plus String pattern, using hash tables to count character frequencies efficiently for substrings.

What is a common mistake when computing the minimum frequency?

A common mistake is including characters with zero occurrences, which incorrectly lowers the minimum frequency and inflates beauty values.

terminal

Solution

Solution 1: Enumeration + Counting

Enumerate the starting position $i$ of each substring, find all substrings with the character at this starting position as the left endpoint, then calculate the beauty value of each substring, and accumulate it to the answer.

1

2

3

4

5

6

7

8

9

class Solution:
    def beautySum(self, s: str) -> int:
        ans, n = 0, len(s)
        for i in range(n):
            cnt = Counter()
            for j in range(i, n):
                cnt[s[j]] += 1
                ans += max(cnt.values()) - min(cnt.values())
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def beautySum(self, s: str) -> int:
        ans, n = 0, len(s)
        for i in range(n):
            cnt = Counter()
            for j in range(i, n):
                cnt[s[j]] += 1
                ans += max(cnt.values()) - min(cnt.values())
        return ans

Continue Practicing

#1790 check if one string swap can make strings equal #1737 change minimum characters to satisfy one of three conditions #1876 substrings of size three with distinct characters