Problem Description

Given a string s, the task is to calculate the sum of the beauty of all its substrings. The beauty of a substring is defined as the difference between the highest frequency and the lowest frequency of characters present in the substring (excluding characters not present in that substring).

• Input: A string s consisting of only lowercase English letters.
• Output: An integer representing the sum of the beauty values for all possible substrings of s.

Constraints:

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

Note: For every substring, only consider characters that appear at least once when computing the minimum frequency.

Thought Process

The first idea that comes to mind is to generate all possible substrings of s and, for each substring, count the frequency of each character. Then, compute the beauty by finding the maximum and minimum frequency (ignoring zeros). Finally, sum up the beauties for all substrings.

However, this brute-force approach can be inefficient, especially since the number of substrings is O(n²) and counting frequencies for each can be O(n), leading to O(n³) time complexity.

To optimize, we can try to reuse frequency data as we expand substrings, reducing redundant computations. We also note that the constraints (string length up to 500) allow for O(n²) solutions, so improving from O(n³) to O(n²) is feasible and desirable.

Solution Approach

Let's break down the optimized solution step by step:

1. Iterate over all possible substrings:
   • For each possible starting index i (from 0 to n-1), expand the substring to every possible ending index j (from i to n-1).
2. Maintain a running frequency count:
   • Use an array of size 26 (for each lowercase letter) to keep track of character counts as the substring grows.
   • For each new character added at position j, increment its count in the array.
3. Compute beauty for the current substring:
   • Find the maximum and minimum non-zero values in the frequency array.
   • The beauty is max_freq - min_freq.
4. Accumulate the total beauty:
   • Add the beauty of each substring to a running total.

This approach ensures that we only need O(1) time to update the frequency array for each substring extension, and O(26) time to compute the beauty, resulting in an overall O(n²) time complexity.

Example Walkthrough

Let's use the input s = "aabcb".

1. Substrings starting at index 0 ("a"):
   • "a": freq = [1,0,0,...], max=1, min=1, beauty=0
   • "aa": freq = [2,0,0,...], max=2, min=2, beauty=0
   • "aab": freq = [2,1,0,...], max=2, min=1, beauty=1
   • "aabc": freq = [2,1,1,...], max=2, min=1, beauty=1
   • "aabcb": freq = [2,2,1,...], max=2, min=1, beauty=1
2. Substrings starting at index 1 ("a"):
   • "a": freq = [1,0,0,...], max=1, min=1, beauty=0
   • "ab": freq = [1,1,0,...], max=1, min=1, beauty=0
   • "abc": freq = [1,1,1,...], max=1, min=1, beauty=0
   • "abcb": freq = [1,2,1,...], max=2, min=1, beauty=1
3. Continue for all other starting indices.
4. Sum all beauties:
   • Total beauty = 5

This demonstrates how we expand substrings, update frequencies, and compute beauties efficiently.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n³) — O(n²) substrings, O(n) to count frequencies for each.
  • Space Complexity: O(1) — Only a frequency array of size 26 needed.
• Optimized approach:
  • Time Complexity: O(n² * 26) = O(n²) — For each substring, updating frequencies and computing max/min over 26 letters.
  • Space Complexity: O(1) — Only a frequency array of size 26 per substring.

The optimized approach is efficient for the given constraints and avoids redundant computations.

Summary

In this problem, we efficiently calculated the sum of the beauty of all substrings by:

• Iterating over all possible substrings using a double loop.
• Maintaining a running frequency count for each substring expansion.
• Computing the beauty by finding the max and min frequency among present characters.
• Optimizing the process to O(n²) time, which is optimal for the given constraints.

Code Implementation

class Solution:
    def beautySum(self, s: str) -> int:
        n = len(s)
        total = 0
        for i in range(n):
            freq = [0] * 26
            for j in range(i, n):
                idx = ord(s[j]) - ord('a')
                freq[idx] += 1
                max_freq = 0
                min_freq = float('inf')
                for f in freq:
                    if f > 0:
                        max_freq = max(max_freq, f)
                        min_freq = min(min_freq, f)
                total += max_freq - min_freq
        return total
      

class Solution {
public:
    int beautySum(string s) {
        int n = s.length();
        int total = 0;
        for (int i = 0; i < n; ++i) {
            int freq[26] = {0};
            for (int j = i; j < n; ++j) {
                freq[s[j] - 'a']++;
                int max_freq = 0, min_freq = INT_MAX;
                for (int k = 0; k < 26; ++k) {
                    if (freq[k] > 0) {
                        max_freq = max(max_freq, freq[k]);
                        min_freq = min(min_freq, freq[k]);
                    }
                }
                total += max_freq - min_freq;
            }
        }
        return total;
    }
};
      

class Solution {
    public int beautySum(String s) {
        int n = s.length();
        int total = 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 = Integer.MAX_VALUE;
                for (int f : freq) {
                    if (f > 0) {
                        maxFreq = Math.max(maxFreq, f);
                        minFreq = Math.min(minFreq, f);
                    }
                }
                total += maxFreq - minFreq;
            }
        }
        return total;
    }
}
      

var beautySum = function(s) {
    let n = s.length;
    let total = 0;
    for (let i = 0; i < n; i++) {
        let freq = new Array(26).fill(0);
        for (let j = i; j < n; j++) {
            freq[s.charCodeAt(j) - 97]++;
            let maxFreq = 0, minFreq = Number.MAX_VALUE;
            for (let f of freq) {
                if (f > 0) {
                    maxFreq = Math.max(maxFreq, f);
                    minFreq = Math.min(minFreq, f);
                }
            }
            total += maxFreq - minFreq;
        }
    }
    return total;
};