Sum of Beauty of All Substrings - Practice Coding Problems

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: 2

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

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

Understanding the Visualization

Input

String with characters that may repeat

Process

For each substring, find max_freq - min_freq

Output

Sum of all beauty values

Key Takeaway

🎯 Key Insight: Beauty is the frequency gap between most and least common characters in each substring

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

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Generate all substrings and calculate beauty for each
Optimized Frequency Tracking	O(n²)	O(1)	Build substrings incrementally while maintaining frequency counts

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler