Calculate Sum of Beauty of All Substrings

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.

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

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.

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.

#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;
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int beautySum(const string& s) {
    int total = 0;
    int n = s.length();

    for (int i = 0; i < n; ++i) {
        vector<int> count(26, 0);
        for (int j = i; j < n; ++j) {
            count[s[j] - 'a']++;
            int maxFreq = 0, minFreq = INT_MAX;
            for (int c : count) {
                if (c > 0) {
                    maxFreq = max(maxFreq, c);
                    minFreq = min(minFreq, c);
                }
            }
            total += (maxFreq - minFreq);
        }
    }
    return total;
}

int main() {
    string s = "aabcb";
    cout << "Sum of Beauty: " << beautySum(s) << endl;
    return 0;
}

def beautySum(s):
    total_beauty = 0
    n = len(s)

    for i in range(n):
        count = [0] * 26
        for j in range(i, n):
            idx = ord(s[j]) - ord('a')
            count[idx] += 1

            freq_list = [c for c in count if c > 0]
            max_freq = max(freq_list)
            min_freq = min(freq_list)

            total_beauty += (max_freq - min_freq)

    return total_beauty

s = "aabcb"
print("Sum of Beauty:", beautySum(s))

public class BeautySumCalculator {
    public static int beautySum(String s) {
        int totalBeauty = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            int[] count = new int[26];
            for (int j = i; j < n; j++) {
                count[s.charAt(j) - 'a']++;

                int max = 0, min = Integer.MAX_VALUE;
                for (int c : count) {
                    if (c > 0) {
                        max = Math.max(max, c);
                        min = Math.min(min, c);
                    }
                }
                totalBeauty += (max - min);
            }
        }
        return totalBeauty;
    }

    public static void main(String[] args) {
        String s = "aabcb";
        System.out.println("Sum of Beauty: " + beautySum(s));
    }
}

function beautySum(s) {
    let totalBeauty = 0;
    const n = s.length;

    for (let i = 0; i < n; i++) {
        const count = new Array(26).fill(0);
        for (let j = i; j < n; j++) {
            count[s.charCodeAt(j) - 97]++;

            const freq = count.filter(c => c > 0);
            const max = Math.max(...freq);
            const min = Math.min(...freq);
            totalBeauty += (max - min);
        }
    }
    return totalBeauty;
}

const s = "aabcb";
console.log("Sum of Beauty:", beautySum(s));

package main

import (
    "fmt"
)

func beautySum(s string) int {
    total := 0
    n := len(s)
    for i := 0; i < n; i++ {
        count := make([]int, 26)
        for j := i; j < n; j++ {
            count[s[j]-'a']++
            maxFreq, minFreq := 0, 1<<31-1
            for _, c := range count {
                if c > 0 {
                    if c > maxFreq {
                        maxFreq = c
                    }
                    if c < minFreq {
                        minFreq = c
                    }
                }
            }
            total += maxFreq - minFreq
        }
    }
    return total
}

func main() {
    s := "aabcb"
    fmt.Println("Sum of Beauty:", beautySum(s))
}

fn beauty_sum(s: &str) -> i32 {
    let mut total = 0;
    let n = s.len();
    let chars: Vec<char> = s.chars().collect();

    for i in 0..n {
        let mut count = [0; 26];
        for j in i..n {
            count[(chars[j] as u8 - b'a') as usize] += 1;
            let freqs: Vec<i32> = count.iter().cloned().filter(|&x| x > 0).collect();
            let max = *freqs.iter().max().unwrap();
            let min = *freqs.iter().min().unwrap();
            total += max - min;
        }
    }
    total
}

fn main() {
    let s = "aabcb";
    println!("Sum of Beauty: {}", beauty_sum(s));
}

fun beautySum(s: String): Int {
    var total = 0
    val n = s.length

    for (i in 0 until n) {
        val count = IntArray(26)
        for (j in i until n) {
            count[s[j] - 'a']++
            val freq = count.filter { it > 0 }
            val max = freq.maxOrNull() ?: 0
            val min = freq.minOrNull() ?: 0
            total += (max - min)
        }
    }
    return total
}

fun main() {
    val s = "aabcb"
    println("Sum of Beauty: ${beautySum(s)}")
}

import Foundation

func beautySum(_ s: String) -> Int {
    let chars = Array(s)
    var total = 0

    for i in 0..<chars.count {
        var count = Array(repeating: 0, count: 26)
        for j in i..<chars.count {
            let idx = Int(chars[j].asciiValue! - Character("a").asciiValue!)
            count[idx] += 1
            let freqs = count.filter { $0 > 0 }
            if let max = freqs.max(), let min = freqs.min() {
                total += (max - min)
            }
        }
    }
    return total
}

let s = "aabcb"
print("Sum of Beauty: \(beautySum(s))")

function beautySum(s: string): number {
    let totalBeauty = 0;
    const n = s.length;

    for (let i = 0; i < n; i++) {
        const count: number[] = Array(26).fill(0);
        for (let j = i; j < n; j++) {
            count[s.charCodeAt(j) - 97]++;
            const freq = count.filter(c => c > 0);
            const max = Math.max(...freq);
            const min = Math.min(...freq);
            totalBeauty += (max - min);
        }
    }
    return totalBeauty;
}

const s: string = "aabcb";
console.log("Sum of Beauty:", beautySum(s));

Time complexity

Space complexity

O(1)

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