Sum of Beauty of All Substrings - Solution & Explanation

Q: Is Sum of Beauty of All Substrings easy or hard?

The problem is rated Medium because the definition of beauty is straightforward but naive implementations are inefficient. The challenge is recognizing that substring frequencies can be updated incrementally to reduce complexity from O(n^3) to O(n^2).

Q: Sum of Beauty of All Substrings Python/Java solution

Python solutions usually use a list of size 26 to store character frequencies while expanding substrings. Java implementations typically use an int array for the same purpose. Both follow the O(n^2) expansion approach and recompute max and min frequencies after each extension.

Q: How to solve Sum of Beauty of All Substrings in O(n)?

A true O(n) algorithm is not known for this problem because every substring potentially contributes a different beauty value. At minimum, substring boundaries must be explored, which leads to O(n^2) enumeration. The commonly accepted optimal approach therefore runs in O(n^2) time.

Q: What is the best approach for Sum of Beauty of All Substrings?

The best practical approach fixes a starting index and expands the substring while maintaining a running frequency array of 26 characters. After each expansion, compute the max and min non‑zero frequencies to calculate the beauty. This reduces redundant work and runs in O(n^2) time with O(1) extra space.

Q: Is Sum of Beauty of All Substrings asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving substring enumeration and frequency counting. Variations of this pattern appear in interviews at companies such as Amazon, Google, and Meta where candidates must efficiently track character frequencies in strings.

Q: What data structure is used in Sum of Beauty of All Substrings?

The main data structure is a frequency counter for characters, typically implemented as a fixed array of size 26 or a hash table. This structure tracks how many times each character appears in the current substring so the maximum and minimum frequencies can be computed.

Q: What is the time complexity of Sum of Beauty of All Substrings?

The optimized solution runs in O(n^2) time because it evaluates every substring starting point and expands the end index while maintaining character counts. Each step scans a constant-size frequency array of 26 letters. Space complexity is O(1).

MediumHash Table String Counting12 min readAsked at: Amazon, Microsoft, Meta +3

Practice this problem

Problem Statement

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.

For example, the beauty of "abaacc" is 3 - 1 = 2.

Given a string s, return the sum of beauty of all of its substrings.

Example 1:

Input: s = "aabcb"
Output: 5
Explanation: 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

Constraints:

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

Approach Overview

Problem Overview: You receive a string s. For every substring, compute its beauty, defined as the difference between the highest character frequency and the lowest non‑zero frequency in that substring. The goal is to sum this beauty value across all possible substrings.

Approach 1: Brute Force Frequency Recalculation (O(n^3) time, O(1) space)

The most direct method enumerates every substring using two indices i and j. For each substring s[i..j], rebuild a frequency array for the 26 lowercase characters, then compute the maximum and minimum non‑zero counts. The beauty value (maxFreq - minFreq) is added to the total. Because you recompute character counts for each substring, the inner operation scans the substring again, producing roughly O(n^3) time. Space stays O(1) since the alphabet size is constant. This approach is simple but inefficient for larger strings.

Approach 2: Optimized Expansion with Running Frequency (O(n^2) time, O(1) space)

A better approach fixes the starting index i and expands the substring one character at a time. Maintain a frequency array of size 26 while extending j. Each step updates the count of s[j], then recomputes the current maximum and minimum non‑zero frequencies by scanning the 26-element array. Since the alphabet is fixed, this scan is constant time. The substring frequencies are reused instead of rebuilt, reducing complexity to O(n^2). This technique relies on efficient character counting using a small array or hash table, combined with incremental substring growth from the string.

Approach 3: Prefix Frequency Precomputation (O(n^2) time, O(26n) space)

You can also build prefix frequency arrays where prefix[i][c] stores how many times character c appears up to index i. For any substring s[l..r], compute each character’s frequency using prefix[r] - prefix[l-1]. After retrieving counts, determine the max and min non‑zero frequencies to calculate the beauty. This avoids maintaining a mutable array while iterating but still requires scanning all 26 characters per substring. The complexity remains O(n^2), with extra memory for prefix storage. It’s a clean approach when working heavily with counting queries across ranges.

Recommended for interviews: The incremental frequency expansion approach is the expected solution. It demonstrates understanding of substring enumeration while avoiding redundant recomputation. Interviewers usually accept O(n^2) because the alphabet is fixed and scanning 26 characters is effectively constant time. Showing the brute force method first proves you understand the definition of beauty, then optimizing with running counts shows practical problem‑solving skill.

Approach 1: Brute Force Approach

This approach involves generating all possible substrings of the input string and calculating the beauty of each substring. The beauty is determined by the frequency difference between the most common and least common character within the substring.

Although straightforward, this approach may be inefficient for larger strings due to the high number of substrings.

The function beauty_sum iterates over all possible substrings of s. For each substring, it maintains a frequency dictionary that is updated as characters are added to the substring. The calc_beauty function computes the beauty of the current substring using the max and min frequencies. The accumulated beauty is the result.

Code

Python C++

Python

C++

Complexity

Time complexity: O(n^3), where n is the length of the string, as it involves generating all substrings and calculating frequencies.

Space complexity: O(1) - as the frequency dictionary size is bounded by the constant number of lowercase letters.

Try this approach in the editor →

Approach 2: Optimized Approach Using Prefix Frequency

This approach reduces repetitive work in calculating frequencies by utilizing prefix frequency arrays that allow efficient substring frequency calculations. For each possible starting point of a substring, update and compute the necessary frequency values from earlier calculations.

This optimized Python solution uses a list of prefix frequency counters. Each counter at index i represents the frequency of characters from the start of the string up to but not including index i. Frequency differences within substrings are obtained using these prefix frequencies. This allows frequency calculation in constant time for each substring.

Code

Python C#

Python

Complexity

Time complexity: O(n^2), where n is the length of the string, as it reduces redundant frequency calculations.

Space complexity: O(n), due to storage of prefix frequency data.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n^2 times C), and the space complexity is O(C). Here, n is the length of the string, and C is the size of the character set. In this problem, C = 26.

Code

Python Java C++Go TypeScript Rust JavaScript

Python

Java

C++

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Default Approach

Code

Python Java C++Go JavaScript

Python

Java

C++

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Brute Force Approach	Time complexity: O(n^3), where n is the length of the string, as it involves generating all substrings and calculating frequencies. Space complexity: O(1) - as the frequency dictionary size is bounded by the constant number of lowercase letters.
Optimized Approach Using Prefix Frequency	Time complexity: O(n^2), where n is the length of the string, as it reduces redundant frequency calculations. Space complexity: O(n), due to storage of prefix frequency data.
Enumeration + Counting	—
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Frequency Recalculation	O(n^3)	O(1)	Useful for understanding the definition of beauty or during early problem exploration
Incremental Frequency Expansion	O(n^2)	O(1)	Best practical solution for interviews and competitive programming
Prefix Frequency Arrays	O(n^2)	O(26n)	Helpful when multiple substring frequency queries are required

Video Solution

7. Sum of Beauty of All Substrings | Strings - Medium | Leetcode 1781 | Learn DSA • Ayushi Sharma • 30,471 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Beauty of All Substrings easy or hard?

The problem is rated Medium because the definition of beauty is straightforward but naive implementations are inefficient. The challenge is recognizing that substring frequencies can be updated incrementally to reduce complexity from O(n^3) to O(n^2).

Sum of Beauty of All Substrings Python/Java solution

Python solutions usually use a list of size 26 to store character frequencies while expanding substrings. Java implementations typically use an int array for the same purpose. Both follow the O(n^2) expansion approach and recompute max and min frequencies after each extension.

How to solve Sum of Beauty of All Substrings in O(n)?

A true O(n) algorithm is not known for this problem because every substring potentially contributes a different beauty value. At minimum, substring boundaries must be explored, which leads to O(n^2) enumeration. The commonly accepted optimal approach therefore runs in O(n^2) time.

What is the best approach for Sum of Beauty of All Substrings?

The best practical approach fixes a starting index and expands the substring while maintaining a running frequency array of 26 characters. After each expansion, compute the max and min non‑zero frequencies to calculate the beauty. This reduces redundant work and runs in O(n^2) time with O(1) extra space.

Is Sum of Beauty of All Substrings asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving substring enumeration and frequency counting. Variations of this pattern appear in interviews at companies such as Amazon, Google, and Meta where candidates must efficiently track character frequencies in strings.

What data structure is used in Sum of Beauty of All Substrings?

The main data structure is a frequency counter for characters, typically implemented as a fixed array of size 26 or a hash table. This structure tracks how many times each character appears in the current substring so the maximum and minimum frequencies can be computed.

What is the time complexity of Sum of Beauty of All Substrings?

The optimized solution runs in O(n^2) time because it evaluates every substring starting point and expands the end index while maintaining character counts. Each step scans a constant-size frequency array of 26 letters. Space complexity is O(1).

Ready to solve this problem?

Practice Sum of Beauty of All Substrings with our built-in code editor and test cases.

Practice on FleetCode

Substrings That Begin and End With the Same Letter

Problem Info

DifficultyMedium

Acceptance74.9%

Approaches4

Reading time12 min

Asked at

Amazon Microsoft Meta Google Zoho

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Brute Force Approach

Code

Complexity

Approach 2: Optimized Approach Using Prefix Frequency

Code

Complexity

Approach 3: Enumeration + Counting

Code

Approach 4: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents