We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Beauty of All Substrings

Difficulty: Medium

Problem Description

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters. Given a string s, return the sum of the beauty of all of its substrings.

Key Insights

  • The beauty of a substring is determined by the frequencies of its characters.
  • Substrings with the same characters can share beauty calculations.
  • We can utilize a frequency counter to track character occurrences efficiently.
  • The challenge lies in calculating the beauty for all possible substrings while avoiding redundant computations.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the string, due to generating all substrings. Space Complexity: O(1), since we only need a fixed-size frequency array for the 26 lowercase English letters.

Solution

To solve this problem, we can use a nested loop to generate all possible substrings of the given string s. For each substring, we will maintain a frequency count of its characters using an array of size 26 (corresponding to the 26 lowercase English letters). After calculating the frequency of each character in a substring, we determine the maximum and minimum frequencies to compute its beauty. We sum the beauties of all substrings to get the final result.

Code Solutions

def beautySum(s):
    total_beauty = 0
    n = len(s)

    for i in range(n):
        freq = [0] * 26  # Frequency array for each character
        for j in range(i, n):
            freq[ord(s[j]) - ord('a')] += 1  # Increment frequency of current character
            max_freq = max(freq)
            min_freq = min(f for f in freq if f > 0)  # Find min frequency of non-zero counts
            total_beauty += max_freq - min_freq  # Calculate beauty for the current substring

    return total_beauty
← Back to All Questions