Sum of Beauty of All Substrings - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "aab"

› Output: 1

💡 Note: Substrings: "a"(beauty=0), "aa"(beauty=0), "aab"(beauty=1), "a"(beauty=0), "ab"(beauty=0), "b"(beauty=0). Total: 0+0+1+0+0+0 = 1

Example 2 — Single Character

$ Input: s = "abc"

› Output: 0

💡 Note: All substrings have equal character frequencies (each char appears once in its substrings), so beauty is always 0

Example 3 — Repeated Characters

$ Input: s = "aaaa"

› Output: 0

💡 Note: All substrings contain only 'a', so max_freq = min_freq, beauty = 0 for all substrings

Constraints

1 ≤ s.length ≤ 500
s consists of only lowercase English letters

Visualization

Tap to expand

Asked in

a Amazon 25 M Microsoft 18

The key insight is to calculate beauty for each substring by finding the difference between maximum and minimum character frequencies. Best approach uses incremental frequency tracking to avoid recalculating frequencies from scratch. Time: O(n²), Space: O(1)

Common Approaches

✓ Brute Force

⏱️ Time: O(n³) Space: O(1)

For every possible substring, count character frequencies and find the difference between maximum and minimum frequencies. Sum all these beauty values.

Optimized Frequency Tracking

⏱️ Time: O(n²) Space: O(1)

For each starting position, extend the substring one character at a time while maintaining a frequency map. This avoids recalculating frequencies from scratch for each substring.

Brute Force — Algorithm Steps

Step 1: Generate all possible substrings
Step 2: For each substring, count character frequencies
Step 3: Calculate beauty (max freq - min freq) and add to total

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings from the input

Count Frequencies

For each substring, count character occurrences

Calculate Beauty

Find max frequency - min frequency for each

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    int totalBeauty = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Count character frequencies in substring s[i...j]
            int freq[26] = {0};
            for (int k = i; k <= j; k++) {
                freq[s[k] - 'a']++;
            }
            
            // Calculate beauty (max_freq - min_freq)
            int maxFreq = 0, minFreq = 1000000;
            for (int k = 0; k < 26; k++) {
                if (freq[k] > 0) {
                    if (freq[k] > maxFreq) maxFreq = freq[k];
                    if (freq[k] < minFreq) minFreq = freq[k];
                }
            }
            
            if (maxFreq > 0) {
                int beauty = maxFreq - minFreq;
                totalBeauty += beauty;
            }
        }
    }
    
    return totalBeauty;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops generate O(n²) substrings, each requiring O(n) time to count frequencies

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for frequency counting (at most 26 characters)

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Sum of Beauty of All Substrings - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler