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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Beauty of All Substrings

Number: 1890

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft

Problem Description

Given a string s, the beauty of a substring is defined as the difference between the highest frequency and the lowest frequency among the characters that occur in the substring. The task is to compute the sum of the beauty for all possible substrings of s.

Key Insights

  • We need to examine every substring of s.
  • For each substring, count the frequency of each character.
  • Compute the maximum and minimum frequency (ignoring characters that do not occur).
  • Use two nested loops while updating the frequency count incrementally to avoid redundant counting.
  • Since there are only 26 lowercase English letters, iterating over them for max and min calculation is efficient.

Space and Time Complexity

Time Complexity: O(n^2 * 26) which simplifies to O(n^2) given the constant factor for 26 letters. Space Complexity: O(26) = O(1) extra space, aside from the input string.

Solution

We use a brute-force approach with optimization. For each starting index i in the string, we maintain a frequency count array for the characters in the current substring. Then, for every ending index j (i ≤ j < n), we update the frequency of the encountered character. For the current substring, we compute the maximum frequency (maxFreq) and the minimum frequency (minFreq) among characters that appear at least once. The difference (maxFreq - minFreq) is the beauty of that substring, and we add it to our total sum. This approach takes advantage of the small constant alphabet size (26 letters) to efficiently compute the beauty for each substring.

Code Solutions

# Python solution for "Sum of Beauty of All Substrings"

def beautySum(s: str) -> int:
    n = len(s)
    total_beauty = 0
    # Loop through each possible substring starting index
    for i in range(n):
        freq = [0] * 26  # frequency counter for letters 'a' to 'z'
        # Expand the substring one character at a time
        for j in range(i, n):
            freq[ord(s[j]) - ord('a')] += 1  # update frequency for the current character
            # Initialize max and min for the current substring
            maxFreq = 0
            minFreq = float('inf')
            # Evaluate only characters that have appeared at least once
            for count in freq:
                if count > 0:
                    maxFreq = max(maxFreq, count)
                    minFreq = min(minFreq, count)
            total_beauty += (maxFreq - minFreq)
    return total_beauty

# Example usage
s = "aabcb"
print(beautySum(s))  # Output: 5
← Back to All Questions