Sum of Beauty of All Substrings

MEDIUM

Description

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.

Example 1:

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:

Input: s = "aabcbaa"
Output: 17

Constraints:

1 <= s.length <=500
s consists of only lowercase English letters.

Approaches

Checkout 2 different approaches to solve Sum of Beauty of All Substrings. Click on different approaches to view the approach and algorithm in detail.

Brute-Force by Generating All Substrings

This approach involves generating every possible substring of the input string s. For each of these substrings, we calculate its beauty and add it to a running total. The beauty is found by first counting character frequencies within the substring and then finding the difference between the maximum and minimum frequency.

Algorithm

Initialize totalBeauty = 0.
Iterate i from 0 to s.length() - 1.
Iterate j from i to s.length() - 1.

Extract the substring `sub = s.substring(i, j + 1)`.

Create a frequency array `freq` of size 26, initialized to zeros.

For each character `c` in `sub`, increment `freq[c - 'a']`.

Find `maxFreq` and `minFreq` from the `freq` array (ignoring zero counts).

Calculate `beauty = maxFreq - minFreq`.

```
Add `beauty` to `totalBeauty`.
```
Return totalBeauty.

The algorithm uses three nested loops. The outer two loops (with indices i and j) are used to define the start and end points of all possible substrings. For each substring sub = s.substring(i, j + 1), a helper function is used to compute its beauty.

To compute the beauty of sub, we first create a frequency map (an array of size 26 for lowercase English letters). We iterate through sub to populate this frequency map. Then, we iterate through the frequency map to find the highest frequency (maxFreq) and the lowest non-zero frequency (minFreq). The beauty of sub is maxFreq - minFreq. This beauty value is added to a total sum. After iterating through all substrings, the total sum is returned.

class Solution {
    public int beautySum(String s) {
        int totalBeauty = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                totalBeauty += calculateBeauty(sub);
            }
        }
        return totalBeauty;
    }

    private int calculateBeauty(String sub) {
        if (sub.length() < 2) {
            return 0;
        }
        int[] freq = new int[26];
        for (char c : sub.toCharArray()) {
            freq[c - 'a']++;
        }

        int maxFreq = 0;
        int minFreq = Integer.MAX_VALUE;
        for (int count : freq) {
            if (count > 0) {
                maxFreq = Math.max(maxFreq, count);
                minFreq = Math.min(minFreq, count);
            }
        }
        return maxFreq - minFreq;
    }
}

Complexity Analysis

Time Complexity: `O(N^3)`, where `N` is the length of the string. There are `O(N^2)` substrings. For each substring of length `L`, calculating its beauty takes `O(L)` time. The sum of lengths of all substrings is `O(N^3)`.Space Complexity: `O(1)` or `O(26)` because the frequency map used for calculating beauty has a constant size.

Pros and Cons

Pros:

Simple to understand and implement.
Directly follows the problem definition.

Cons:

Highly inefficient due to redundant calculations. The frequency map for each substring is computed from scratch.
Likely to result in a 'Time Limit Exceeded' (TLE) error for larger inputs (like N=500).

Code Solutions

Checking out 4 solutions in different languages for Sum of Beauty of All Substrings. Click on different languages to view the code.

class Solution {
public
  int beautySum(String s) {
    int ans = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      int[] cnt = new int[26];
      for (int j = i; j < n; ++j) {
        ++cnt[s.charAt(j) - 'a'];
        int mi = 1000, mx = 0;
        for (int v : cnt) {
          if (v > 0) {
            mi = Math.min(mi, v);
            mx = Math.max(mx, v);
          }
        }
        ans += mx - mi;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Sum of Beauty of All Substrings

Patterns:

Counting

Data Structures:

Hash TableString

Companies:

Fastenal |