Sum Of Beauty Of All Substrings - Leetcode Solution

The problem "Sum Of Beauty Of All Substrings" on LeetCode asks you to find the sum of the beauty of all substrings of a given string.

To solve this problem, we can use a brute force approach where we iterate over all possible substrings and calculate their beauty. However, this approach has a time complexity of O(n^3), which is not efficient for large input sizes.

Instead, we can use a more optimized approach where we iterate over the string once and calculate the beauty of each substring using a frequency table. The beauty of a substring can be calculated by finding the difference between the maximum and minimum frequency of the characters in the substring.

We start by initializing a variable 'totalBeauty' to 0. We also create an array 'freqTable' of size 26 to keep track of the frequency of each character in the current substring.

We then iterate over the string and for each character, we update the frequency table. We also calculate the maximum and minimum frequency of the characters in the current substring.

Once we have calculated the maximum and minimum frequency, we subtract the minimum frequency from the maximum frequency to get the beauty of the current substring. We add this beauty to the 'totalBeauty' variable.

Finally, we return the 'totalBeauty' variable as the solution.

Here is the code in Python:

def beautySum(s: str) -> int:
    n = len(s)
    totalBeauty = 0

    for i in range(n):
        freqTable = [0] * 26
        maxFreq = 0
        minFreq = n

        for j in range(i, n):
            freqTable[ord(s[j]) - 97] += 1
            maxFreq = max(maxFreq, freqTable[ord(s[j]) - 97])
            minFreq = min(minFreq, freqTable[ord(s[j]) - 97])
            totalBeauty += maxFreq - minFreq

    return totalBeauty

The time complexity of this solution is O(n^2) since we iterate over the string once and for each character, we iterate over the remaining characters to calculate the frequency table and beauty of the substring.

The space complexity is O(26) since we use a constant amount of space to store the frequency table.

1