How do you solve Sum of Beauty of All Substrings on LeetCode?

Sum of Beauty of All Substrings (LeetCode #1781) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: The beauty of a substring is determined by the frequency of characters.

What is the brute force solution for Sum of Beauty of All Substrings?

The brute force approach for Sum of Beauty of All Substrings is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible substrings of the given string and calculating the beauty of each substring. This is straightforward but inefficient for larger strings. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Sum of Beauty of All Substrings?

Sum of Beauty of All Substrings uses the following concepts: Hash Table, String, Counting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Sum of Beauty of All Substrings?

Think about how to optimize substring calculations instead of generating them explicitly. Practice calculating character frequencies efficiently. Be prepared to explain your thought process clearly during the interview.

What are common mistakes when solving Sum of Beauty of All Substrings?

Not handling cases where all characters are the same, leading to incorrect beauty calculations. Forgetting to reset frequency counts for new starting indices.

#1781

Sum of Beauty of All Substrings

Medium

Hash TableStringCountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution uses a sliding window approach combined with a frequency count to efficiently calculate the beauty of all substrings without generating them explicitly. This reduces redundant calculations.

⚙️

Algorithm

4 steps

1Step 1: Initialize a frequency array to count character occurrences.
2Step 2: Use two pointers to define the current substring window.
3Step 3: For each window, update the frequency array and calculate the beauty by finding the max and min frequencies.
4Step 4: Sum the beauties for all valid substrings.

solution.py14 lines

1def beautySum(s):
2    total_beauty = 0
3    n = len(s)
4    for i in range(n):
5        freq = [0] * 26
6        max_freq = 0
7        min_freq = float('inf')
8        for j in range(i, n):
9            freq[ord(s[j]) - ord('a')] += 1
10            max_freq = max(max_freq, freq[ord(s[j]) - ord('a')])
11            min_freq = min(min_freq, freq[ord(s[j]) - ord('a')]) if freq[ord(s[j]) - ord('a')] > 0 else min_freq
12            if min_freq != float('inf'):
13                total_beauty += max_freq - min_freq
14    return total_beauty

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops for substrings, but we optimize the beauty calculation using a frequency array. The space complexity is O(1) since the frequency array size is constant (26 for lowercase letters).

1The beauty of a substring is determined by the frequency of characters.
2Using frequency arrays can optimize the calculation of max and min frequencies.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.