Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sum of Beauty of All Substrings

MEDIUMProblemSolveExternal Links

Description

The beauty of a string is defined as the difference between the frequency of the most frequent character and the frequency of the least frequent character in that string.

For example, for the string "abaacc":

  • Character frequencies: a → 3, b → 1, c → 2
  • Most frequent = 3 (character 'a'), Least frequent = 1 (character 'b')
  • Beauty = 3 − 1 = 2

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

A substring is a contiguous sequence of characters within the string. Note that we only consider characters that actually appear in the substring when determining the least frequent character.

Examples

Example 1

Input: s = "aabcb"

Output: 5

Explanation: The substrings that have a non-zero beauty are:

  • "aab" → frequencies: a=2, b=1 → beauty = 2 − 1 = 1
  • "aabc" → frequencies: a=2, b=1, c=1 → beauty = 2 − 1 = 1
  • "aabcb" → frequencies: a=2, b=2, c=1 → beauty = 2 − 1 = 1
  • "abcb" → frequencies: a=1, b=2, c=1 → beauty = 2 − 1 = 1
  • "bcb" → frequencies: b=2, c=1 → beauty = 2 − 1 = 1

All other substrings have beauty 0 (either single characters or all characters have equal frequency).

Total beauty = 1 + 1 + 1 + 1 + 1 = 5.

Example 2

Input: s = "aabcbaa"

Output: 17

Explanation: There are many substrings with non-zero beauty in this longer string. The sum of all their beauties totals to 17.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to consider every possible substring, compute its beauty, and add all beauties together.

Think of it like examining every possible window you can cut out of a ribbon of letters. For each window, you count how many times each letter appears, find the most common and least common letters, and record the gap between their counts.

Since a string of length n has n×(n+1)/2 substrings, and for each substring we need to count character frequencies from scratch, this approach does a lot of repeated work. For each substring, we scan its entire length to build a frequency map, then scan the frequency map to find the max and min frequencies.

Step-by-Step Explanation

Let's trace through with s = "aabcb":

We enumerate all substrings of length ≥ 2 (single characters always have beauty 0).

Step 1: Substring "aa" (i=0, j=1): frequencies a=2. Only one distinct character, so max_freq = min_freq = 2. Beauty = 0.

Step 2: Substring "aab" (i=0, j=2): frequencies a=2, b=1. max_freq=2, min_freq=1. Beauty = 2 − 1 = 1. Running total = 1.

Step 3: Substring "aabc" (i=0, j=3): frequencies a=2, b=1, c=1. max_freq=2, min_freq=1. Beauty = 1. Running total = 2.

Step 4: Substring "aabcb" (i=0, j=4): frequencies a=2, b=2, c=1. max_freq=2, min_freq=1. Beauty = 1. Running total = 3.

Step 5: Substring "ab" (i=1, j=2): frequencies a=1, b=1. max_freq = min_freq = 1. Beauty = 0.

Step 6: Substring "abc" (i=1, j=3): frequencies a=1, b=1, c=1. max_freq = min_freq = 1. Beauty = 0.

Step 7: Substring "abcb" (i=1, j=4): frequencies a=1, b=2, c=1. max_freq=2, min_freq=1. Beauty = 1. Running total = 4.

Step 8: Substring "bc" (i=2, j=3): frequencies b=1, c=1. Beauty = 0.

Step 9: Substring "bcb" (i=2, j=4): frequencies b=2, c=1. max_freq=2, min_freq=1. Beauty = 1. Running total = 5.

Step 10: Substring "cb" (i=3, j=4): frequencies c=1, b=1. Beauty = 0.

Result: Total beauty = 5.

Brute Force — Checking All Substrings for Beauty — Watch how we examine every possible substring, count character frequencies from scratch, and compute the beauty as max_freq minus min_freq.

Algorithm

  1. Initialize total_beauty = 0.
  2. For each starting index i from 0 to n−1:
    a. For each ending index j from i to n−1:
    • Extract substring s[i..j]
    • Count the frequency of each character in this substring
    • Find max_freq (highest frequency) and min_freq (lowest frequency among characters that appear)
    • Add (max_freq − min_freq) to total_beauty
  3. Return total_beauty.

Code

class Solution {
public:
    int beautySum(string s) {
        int n = s.length();
        int totalBeauty = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Count frequencies for substring s[i..j]
                int freq[26] = {0};
                for (int k = i; k <= j; k++) {
                    freq[s[k] - 'a']++;
                }
                
                int maxFreq = 0, minFreq = n + 1;
                for (int c = 0; c < 26; c++) {
                    if (freq[c] > 0) {
                        maxFreq = max(maxFreq, freq[c]);
                        minFreq = min(minFreq, freq[c]);
                    }
                }
                totalBeauty += (maxFreq - minFreq);
            }
        }
        
        return totalBeauty;
    }
};
class Solution:
    def beautySum(self, s: str) -> int:
        n = len(s)
        total_beauty = 0
        
        for i in range(n):
            for j in range(i + 1, n):
                # Count frequencies for substring s[i..j]
                freq = {}
                for k in range(i, j + 1):
                    freq[s[k]] = freq.get(s[k], 0) + 1
                
                max_freq = max(freq.values())
                min_freq = min(freq.values())
                total_beauty += (max_freq - min_freq)
        
        return total_beauty
class Solution {
    public int beautySum(String s) {
        int n = s.length();
        int totalBeauty = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Count frequencies for substring s[i..j]
                int[] freq = new int[26];
                for (int k = i; k <= j; k++) {
                    freq[s.charAt(k) - 'a']++;
                }
                
                int maxFreq = 0, minFreq = n + 1;
                for (int c = 0; c < 26; c++) {
                    if (freq[c] > 0) {
                        maxFreq = Math.max(maxFreq, freq[c]);
                        minFreq = Math.min(minFreq, freq[c]);
                    }
                }
                totalBeauty += (maxFreq - minFreq);
            }
        }
        
        return totalBeauty;
    }
}

Complexity Analysis

Time Complexity: O(n³)

We have two nested loops to enumerate all O(n²) substrings. For each substring, we scan its entire length (up to O(n)) to count character frequencies. This gives us O(n²) × O(n) = O(n³). Additionally, finding max and min frequency requires scanning 26 entries, which is O(1) per substring.

Space Complexity: O(1)

We use a fixed-size frequency array of 26 entries for each substring. This does not grow with input size, so space is constant.

Why This Approach Is Not Efficient

With n up to 500, the brute force performs roughly 500³ = 125,000,000 operations. While this may fit within time limits for smaller inputs, it is inefficient because we are recomputing the frequency map from scratch for every substring.

Consider: the substring s[i..j] and s[i..j+1] share nearly all their characters — the only difference is one additional character at position j+1. Yet the brute force throws away the entire frequency count and rebuilds it.

Key insight: instead of rebuilding the frequency map for each substring, we can incrementally update it. When extending a substring by one character, we simply increment that character's frequency. This eliminates the innermost loop entirely.

Optimal Approach - Incremental Frequency Counting

Intuition

Instead of recounting all characters for every substring, we can exploit the fact that substrings with the same starting point grow by one character at a time.

Imagine you are reading a book and counting word frequencies. When you read one more page, you do not re-read the entire book from the beginning — you simply update your counts with the new words on that page.

Similarly, for a fixed starting index i, as we extend the end index j from i to n−1, we maintain a running frequency array. Each time j advances by 1, we increment the count for the new character s[j]. Then we scan the 26-entry frequency array to find the current max and min frequencies.

Since scanning 26 entries is O(1) (constant, independent of n), this approach runs in O(n²) time overall — a significant improvement over O(n³).

Step-by-Step Explanation

Let's trace through with s = "aabcb":

Step 1: Fix i=0. Initialize empty frequency array. Process characters one by one.

Step 2: j=0, add 'a' → freq = {a:1}. Only one character, beauty = 1−1 = 0.

Step 3: j=1, add 'a' → freq = {a:2}. Still one distinct character, beauty = 2−2 = 0.

Step 4: j=2, add 'b' → freq = {a:2, b:1}. max_freq=2, min_freq=1, beauty=1. Total=1.

Step 5: j=3, add 'c' → freq = {a:2, b:1, c:1}. max_freq=2, min_freq=1, beauty=1. Total=2.

Step 6: j=4, add 'b' → freq = {a:2, b:2, c:1}. max_freq=2, min_freq=1, beauty=1. Total=3.

Step 7: Fix i=1. Reset frequency array. Process characters from index 1.

Step 8: j=1, add 'a' → freq = {a:1}. Beauty=0.

Step 9: j=2, add 'b' → freq = {a:1, b:1}. max=min=1, beauty=0.

Step 10: j=3, add 'c' → freq = {a:1, b:1, c:1}. All equal, beauty=0.

Step 11: j=4, add 'b' → freq = {a:1, b:2, c:1}. max=2, min=1, beauty=1. Total=4.

Step 12: Fix i=2. Reset. j=2 add 'b' → {b:1}, beauty=0. j=3 add 'c' → {b:1,c:1}, beauty=0. j=4 add 'b' → {b:2,c:1}, max=2, min=1, beauty=1. Total=5.

Step 13: Fix i=3. j=3 add 'c' → {c:1}, beauty=0. j=4 add 'b' → {c:1,b:1}, beauty=0.

Step 14: Fix i=4. j=4 add 'b' → {b:1}, beauty=0.

Result: Total beauty = 5.

Optimal — Incremental Frequency Update — Watch how we maintain a running frequency count for each starting position, adding one character at a time instead of recounting from scratch.

Algorithm

  1. Initialize total_beauty = 0.
  2. For each starting index i from 0 to n−1:
    a. Initialize a frequency array of size 26, all zeros.
    b. For each ending index j from i to n−1:
    • Increment freq[s[j] - 'a'] by 1 (add the new character)
    • Scan the frequency array to find max_freq and min_freq (considering only non-zero entries)
    • Add (max_freq - min_freq) to total_beauty
  3. Return total_beauty.

Code

class Solution {
public:
    int beautySum(string s) {
        int n = s.length();
        int totalBeauty = 0;
        
        for (int i = 0; i < n; i++) {
            int freq[26] = {0};
            
            for (int j = i; j < n; j++) {
                freq[s[j] - 'a']++;
                
                int maxFreq = 0, minFreq = n + 1;
                for (int c = 0; c < 26; c++) {
                    if (freq[c] > 0) {
                        maxFreq = max(maxFreq, freq[c]);
                        minFreq = min(minFreq, freq[c]);
                    }
                }
                totalBeauty += (maxFreq - minFreq);
            }
        }
        
        return totalBeauty;
    }
};
class Solution:
    def beautySum(self, s: str) -> int:
        n = len(s)
        total_beauty = 0
        
        for i in range(n):
            freq = [0] * 26
            
            for j in range(i, n):
                freq[ord(s[j]) - ord('a')] += 1
                
                max_freq = 0
                min_freq = n + 1
                for count in freq:
                    if count > 0:
                        max_freq = max(max_freq, count)
                        min_freq = min(min_freq, count)
                
                total_beauty += (max_freq - min_freq)
        
        return total_beauty
class Solution {
    public int beautySum(String s) {
        int n = s.length();
        int totalBeauty = 0;
        
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                
                int maxFreq = 0, minFreq = n + 1;
                for (int c = 0; c < 26; c++) {
                    if (freq[c] > 0) {
                        maxFreq = Math.max(maxFreq, freq[c]);
                        minFreq = Math.min(minFreq, freq[c]);
                    }
                }
                totalBeauty += (maxFreq - minFreq);
            }
        }
        
        return totalBeauty;
    }
}

Complexity Analysis

Time Complexity: O(n² × 26) = O(n²)

The outer loop runs n times. The inner loop runs up to n times for each starting index. For each substring extension, we do O(1) work to update the frequency and O(26) work to scan the frequency array for max/min. Since 26 is a constant (the size of the alphabet), the overall complexity is O(n² × 26) which simplifies to O(n²).

With n ≤ 500, this means at most 500² × 26 ≈ 6.5 million operations — well within typical time limits.

Space Complexity: O(1)

We use a frequency array of fixed size 26 (one slot per lowercase letter). This does not grow with the input size, so space complexity is constant O(1).