Sum of Beauty of All Substrings - Visualization

Strings

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given a string s, your task is to find the sum of beauty for all its substrings.

The beauty of a substring is defined as the difference between the highest frequency character and the lowest frequency character (ignoring characters that do not appear).

For example, in substring "aabcb", the frequencies are: a → 2, b → 2, c → 1. So the beauty is 2 - 1 = 1.

You need to compute this value for every possible substring of s and return the total sum of all these beauties.

Examples❯

Input String Output Description
"aabcb" 5 Each substring is checked for character frequency difference. Total beauty = 5
"abcab" 5 Beauty is computed for substrings like "abc", "bca", etc.
"aaaa" 0 All characters are the same in every substring, so beauty = 0
"ab" 0 Each substring has unique characters or equal frequencies
"a" 0 Only one character. No frequency difference
"" 0 Empty string has no substrings. Answer is 0

Solution❯

Understanding the Problem

We are given a string, and we need to calculate the total beauty of all its substrings. But what does "beauty" mean in this context?

The beauty of a substring is defined as the difference between the highest frequency and the lowest frequency (excluding zero) of characters present in that substring.

So for each possible substring, we:

  • Count how many times each character appears.
  • Ignore characters with zero frequency.
  • Calculate the difference between the maximum and minimum frequencies among the present characters.

We need to do this for every possible substring of the string and add up all the beauty values.

Step-by-Step Solution with Example

Step 1: Initialize total beauty counter

We'll keep a counter to store the total beauty of all substrings. Let’s call it totalBeauty.

Step 2: Loop through all possible substrings

We use two nested loops: the outer loop sets the starting index of the substring, and the inner loop expands the end index.

Step 3: Maintain a character frequency count

As we expand the substring, we maintain a frequency array of size 26 (for each lowercase English letter).

Step 4: For each substring, compute beauty

After updating the frequency array:

  • Extract all non-zero frequencies.
  • Find the maximum and minimum among them.
  • Beauty = max - min
  • Add this to totalBeauty

Step 5: Example with string "aabcb"

Let's go through a few substrings:

  • "a" → freq: {a:1} → max = 1, min = 1 → beauty = 0
  • "aa" → freq: {a:2} → max = 2, min = 2 → beauty = 0
  • "aab" → freq: {a:2, b:1} → max = 2, min = 1 → beauty = 1
  • "aabc" → freq: {a:2, b:1, c:1} → max = 2, min = 1 → beauty = 1
  • ... and so on
We repeat this for all substrings and sum the beauty values.

Edge Cases

Case 1: All characters are the same

Example: "aaaa"
Every substring has the same character only, so max and min frequency are equal → beauty = 0 for all substrings.

Case 2: All characters are unique

Example: "abc"
Substrings like "ab", "bc", or "abc" have equal frequency for each character → beauty = 0.
But substrings like "a" or "b" still count as well, with beauty = 0.

Case 3: Short strings

Example: "a" → Only one character → max = min = 1 → beauty = 0

Example: "ab" → Both characters appear once → max = min = 1 → beauty = 0

Case 4: Empty string

No substrings to evaluate → total beauty = 0

Finally

This problem is a great exercise in brute-force with optimization. Even though the naive approach is O(n³), we can optimize to roughly O(n²) by reusing frequency arrays as we expand the substring.

Always remember to handle edge cases and think about the substring growth patterns. For large strings, this frequency-count-based method helps manage performance effectively.

Algorithm Steps❯

  1. Initialize a variable totalBeauty = 0.
  2. Loop over each start index i of the string.
  3. Initialize a frequency array count[26] for characters 'a' to 'z'.
  4. For each end index j ≥ i, do:
  5. → Increment the count of character s[j].
  6. → Find maxFreq and minFreq from the count array (ignoring 0s).
  7. → Add (maxFreq - minFreq) to totalBeauty.
  8. Return totalBeauty.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <string.h>

int beautySum(char* s) {
    int total = 0, n = strlen(s);

    for (int i = 0; i < n; i++) {
        int count[26] = {0};
        for (int j = i; j < n; j++) {
            count[s[j] - 'a']++;
            int max = 0, min = 1000;
            for (int k = 0; k < 26; k++) {
                if (count[k] > 0) {
                    if (count[k] > max) max = count[k];
                    if (count[k] < min) min = count[k];
                }
            }
            total += (max - min);
        }
    }
    return total;
}

int main() {
    char s[] = "aabcb";
    printf("Sum of Beauty: %d\n", beautySum(s));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n^2)We iterate through all possible substrings (n^2 combinations), and each frequency check takes constant time.
Average CaseO(n^2)The main loop processes all substrings, and frequency difference is computed in O(26) = O(1).
Worst CaseO(n^2)Even if all characters are distinct, the double loop covers all substrings of the input string.

Space Complexity❯

O(1)

Explanation: Only a fixed-size array of 26 elements is used for frequency counting.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...