1781. Sum of Beauty of All Substrings

MediumHash TableStringCounting

Problem Description

The problem asks us to calculate the "beauty" of a string. The beauty of a string is defined as the difference between the number of occurrences of the most frequent character and the least frequent character in that string. We are to find the beauty of every possible substring of the given string and then sum up these beauties to get a final answer.

Substrings of a string are the sequences of characters that can be derived from the string by deleting some characters (possibly, none) from the beginning or end of the string. For instance, "ab", "b", "baa", etc. are all substrings of the string "abaacc".

To further clarify the problem, let's take the example given in the problem description: For the string "abaacc", the beauty of this string is calculated by looking at the frequency of each character. The character 'a' appears 3 times, 'b' once, and 'c' twice. The most frequent character is 'a', with a frequency of 3, and the least frequent (excluding characters not present at all) is 'b', with a frequency of 1. So, the beauty of the string "abaacc" is 3 - 1 = 2.

What the problem ultimately requires us to do is calculate such beauties for all substrings of the input string 's' and return their sum.

Intuition

The solution adopts a brute-force approach to finding all possible substrings and calculating the beauty of each. Breaking down our approach intuitively:

We will iterate over every possible starting point for a substring within the string 's'. This is done by a loop indexed by 'i' going from the start to the end of 's'.
For each starting point 'i', we will then iterate over all possible ending points. These are determined by the loop indexed by 'j', which goes from 'i' to the end of 's'.
As we expand our substring from 'i' to 'j', we will keep track of the frequencies of the characters appearing in the substring using a Counter (which is essentially a specialized dictionary or hash map provided by Python's collections library).
At each iteration, as we increase the size of the current substring by extending 'j', we calculate the beauty of the new substring by finding the frequency of the most and least frequent characters in our Counter. This is the difference between max(cnt.values()) and min(cnt.values()).
We add this beauty to a running total 'ans', which, at the end of the process, will contain the sum of beauties of all substrings.

The brute-force solution may not be the most efficient, especially for very long strings, because the number of substrings grows rapidly. However, it is a straightforward method that guarantees a correct solution by exhaustively checking every option.

Solution Approach

The implementation of the provided solution follows a brute-force approach and iteratively calculates the beauty of all possible substrings of the input string. Let's delve into the specifics:

Two Nested Loops: The algorithm uses two nested loops, which enables it to consider every possible substring of the input string. The outer loop (indexed by i) represents the start of the substring, while the inner loop (indexed by j) represents the end.
Counter: A Counter from Python's collections library is used to track character frequencies within the current substring. This data structure allows us to efficiently keep a tally as we extend our substring by adding characters one by one.
Updating Counter: Within the inner loop, the counter is updated every time a new character is added to the substring: cnt[s[j]] += 1. This line increments the count of the character at the current end position j.
Calculating Beauty: After each update to the counter, the beauty of the new substring is determined by finding the maximum and minimum values of cnt. This is executed by max(cnt.values()) - min(cnt.values()). It represents the frequency of the most common character minus the frequency of the least common character in the current substring.
Summing Up the Beauties: The beauty found at each step is then added to a running total ans, which eventually becomes the answer. This occurs in the expression ans += max(cnt.values()) - min(cnt.values()).
Returning the Result: After all iterations, the outer loop concludes, and the final value of ans—which, at this point, holds the accumulated beauty of all substrings—is returned as the result of the function.

This algorithm is straightforward but not particularly efficient, as it has a time complexity of O(n^3) considering that there are n*(n+1)/2 possible substrings and for each substring we are computing the beauty in O(n) time. This is an exhaustive method that guarantees the correct summation of the beauties for all substrings but might not scale well for large strings due to its polynomial time complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small string "abc" to illustrate the solution approach.

For this string "abc", the possible substrings along with their beauties (difference between most frequent and least frequent character counts) will be:

"a" -> Beauty: 0 (since there is only one character)
"b" -> Beauty: 0 (since there is only one character)
"c" -> Beauty: 0 (since there is only one character)
"ab" -> Beauty: 0 (both 'a' and 'b' occur exactly once)
"bc" -> Beauty: 0 (both 'b' and 'c' occur exactly once)
"abc" -> Beauty: 0 (all characters 'a', 'b', and 'c' occur exactly once)

Now, following the solution approach steps:

Two Nested Loops: We start with the outer loop where i goes from 0 to 2 (the length of the string - 1) to take each character as the starting point. For each value of i, we enter the inner loop, where j also ranges from i to 2.
Counter: We initialize an empty Counter object cnt at the start of each iteration of the outer loop because we are starting a new substring.
Updating Counter: For each pair (i, j), we increment the count of s[j] in our Counter by 1, thereby updating the frequency of the current character.
Calculating Beauty: We then calculate the beauty of this particular substring as max(cnt.values()) - min(cnt.values()). Since all characters in our substrings occur at most once, this beauty is always 0 in the case of the example string "abc".
Summing Up the Beauties: For each new substring, the calculated beauty (which is always 0 for our example "abc") is added to the running total ans.
Returning the Result: After all iterations of both loops, we conclude that the sum of the beauties is 0 since all our substrings have characters appearing only once.

Therefore, for the input string "abc", our function would return the sum of the beauties of all substrings, which is 0 in this case. Remember, this method does indeed scale poorly for larger strings, as it must compute the beauty of each substring individually, which becomes exponentially greater as the length of the string increases.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def beautySum(self, s: str) -> int:
5        # Initialize the sum to store the total beauty of all substrings
6        total_beauty = 0
7        # Get the length of the string
8        string_length = len(s)
9      
10        # Iterate through each character in the string as the starting point
11        for i in range(string_length):
12            # Create a counter to keep track of the frequency of each character in the current substring
13            char_counter = Counter()
14            # Iterate from the current character to the end of the string to form substrings
15            for j in range(i, string_length):
16                # Increment the count of the current character
17                char_counter[s[j]] += 1
18                # Calculate the beauty of the current substring by finding the 
19                # difference between the max and min frequency of characters
20                current_beauty = max(char_counter.values()) - min(char_counter.values())
21                # Add the beauty of the current substring to the total beauty
22                total_beauty += current_beauty
23        # Return the total beauty of all substrings
24        return total_beauty
25

1class Solution {
2    public int beautySum(String s) {
3        int totalBeauty = 0; // This will hold the cumulative beauty sum
4        int stringLength = s.length(); // Store the length of string s
5
6        // Outer loop to go through the substring starting points
7        for (int i = 0; i < stringLength; ++i) {
8            int[] frequencyCount = new int[26]; // Frequency array to count letters in the substring
9
10            // Inner loop to go through the substrings ending with character at position j
11            for (int j = i; j < stringLength; ++j) {
12                // Increment the frequency count of current character
13                ++frequencyCount[s.charAt(j) - 'a'];
14
15                // Set initial max and min frequency of characters. 1000 is assumed to be greater
16                // than any possible frequency thus a decent starting value for the minimum.
17                int minFrequency = 1000, maxFrequency = 0;
18
19                // Loop through the frequency count array to find the highest and lowest frequency
20                // that is greater than zero (character is present)
21                for (int freq : frequencyCount) {
22                    if (freq > 0) {
23                        minFrequency = Math.min(minFrequency, freq);
24                        maxFrequency = Math.max(maxFrequency, freq);
25                    }
26                }
27
28                // Beauty is calculated as the difference between max and min frequency of
29                // characters in the substring. Add this to totalBeauty.
30                totalBeauty += maxFrequency - minFrequency;
31            }
32        }
33
34        // Return the cumulative beauty of all substrings
35        return totalBeauty;
36    }
37}
38

1class Solution {
2public:
3    // This function calculates the beauty sum of a string.
4    int beautySum(string s) {
5        int sum = 0; // Initialize sum to store the beauty sum result.
6        int n = s.size(); // Get the size of the string.
7        int charCounts[26]; // Array to count occurrences of each character (a-z).
8
9        // Iterate over the string starting with substrings of length 1 to n.
10        for (int start = 0; start < n; ++start) {
11            memset(charCounts, 0, sizeof charCounts); // Reset character counts for each new starting point.
12            // Explore all substrings starting at 'start' and ending at 'end'.
13            for (int end = start; end < n; ++end) {
14                // Increment the count of the current character.
15                ++charCounts[s[end] - 'a'];
16
17                // Initialize max and min occurrences of characters found so far.
18                int minFreq = 1000, maxFreq = 0; 
19                // Iterate over the counts to find the max and min frequencies.
20                for (int count : charCounts) {
21                    if (count > 0) { // Only consider characters that appear in the substring.
22                        minFreq = min(minFreq, count);
23                        maxFreq = max(maxFreq, count);
24                    }
25                }
26                // Add the beauty (difference between max and min frequency) of this substring to the sum.
27                sum += maxFreq - minFreq;
28            }
29        }
30        // Return the total beauty sum of all substrings.
31        return sum;
32    }
33};
34

1/**
2 * Calculates the sum of beauty of all of its substrings.
3 * @param {string} s - The string to process.
4 * @return {number} - The sum of beauty of all substrings.
5 */
6const beautySum = (s: string): number => {
7    let beautySumResult: number = 0;
8    // Iterate through the string
9    for (let i = 0; i < s.length; ++i) {
10        // Keep track of the frequency of each character
11        const frequencyCounter: Map<string, number> = new Map();
12        // Consider all substrings starting with the character at index 'i'
13        for (let j = i; j < s.length; ++j) {
14            // Increment the frequency of the current character
15            frequencyCounter.set(s[j], (frequencyCounter.get(s[j]) || 0) + 1);
16            // Extract frequency values from the map to determine beauty
17            const frequencies: number[] = Array.from(frequencyCounter.values());
18            // The beauty of the substring is defined by the difference
19            // between the max and min frequency chars
20            beautySumResult += Math.max(...frequencies) - Math.min(...frequencies);
21        }
22    }
23    // Return the total beauty sum of all substrings
24    return beautySumResult;
25};
26
27// The function can be used as follows:
28// const result: number = beautySum("yourStringHere");
29

Time and Space Complexity

Time Complexity

The provided code has two nested loops: the outer loop (indexed by i) iterating over the starting points in the string s, and the inner loop (indexed by j) iterating over the endpoints extending from the current starting point. For each inner iteration, it updates the Counter and calculates the beauty of the current substring.

The outer loop runs n times (where n is the length of s). For each iteration of i, the inner loop runs up to n-i times. In the worst case, where i is 0, the inner loop runs n times, and in the best case, where i is n-1, it runs once.

The update and calculation within the inner loop take O(k) time in the worst case, where k is the number of distinct characters in s since the Counter needs to iterate over all the keys to find the max and min values.

Therefore, the total time complexity is O(n^2 * k) where n is the length of the string and k is the number of unique characters.

Space Complexity

The space complexity is dictated by the Counter which stores the frequency of each character in the current substring.

In the worst case, the substring could contain all unique characters of the string. Hence, the space complexity is O(k) where k is the number of unique characters in the string s.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers