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.

Examples

Example 1:

1
2
3

Input: s = "aabcb"
Output: 5
Explanation: The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.

Example 2:

1
2

Input: s = "aabcbaa"
Output: 17

Solution

Method 1 - Naive

To solve this problem, we need to iterate through all substrings of the given string s and calculate the beauty of each substring. Given that a substring’s beauty is the difference between the maximum and minimum frequency of its characters, we can follow a brute-force approach and optimise it to some extent.

Approach

  1. Generate All Substrings:
    • Iterate over all possible substrings of s.
    • For each substring, construct a frequency count of characters.
  2. Calculate Beauty:
    • For each substring, determine the maximum and minimum frequency of the characters.
    • Calculate the beauty as the difference between the maximum and minimum counts.
  3. Sum the Beauty Values:
    • Sum up the beauty values for all substrings to get the desired result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int beautySum(String s) {
        int n = s.length();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];  // Frequency array for characters 'a' to 'z'
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                ans += beauty(freq);
            }
        }

        return ans;
    }

    private int beauty(int[] freq) {
        int maxFreq = 0;
        int minFreq = Integer.MAX_VALUE;
        for (int f : freq) {
            if (f > 0) {
                maxFreq = Math.max(maxFreq, f);
                minFreq = Math.min(minFreq, f);
            }
        }
        return maxFreq - minFreq;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def beautySum(self, s: str) -> int:
        def beauty(freq: list[int]) -> int:
            max_freq = max(freq)
            min_freq = min(f for f in freq if f > 0)
            return max_freq - min_freq

        n: int = len(s)
        ans: int = 0

        for i in range(n):
            freq = [0] * 26  # Frequency array for characters 'a' to 'z'
            for j in range(i, n):
                freq[ord(s[j]) - ord('a')] += 1
                ans += beauty(freq)

        return ans

Complexity

  • ⏰ Time complexity: O(n^3), where n is the length of the string s. This is because:
    • Generating all substrings takes O(n^2) time.
    • For each substring, calculating the beauty by counting character frequencies takes O(n) time.
  • 🧺 Space complexity: O(1) for the frequency array since it’s fixed at 26 (for lowercase English letters) for every substring.