1781. Sum of Beauty of All Substrings LeetCode Solution

In this guide, you will get 1781. Sum of Beauty of All Substrings LeetCode Solution with the best time and space complexity. The solution to Sum of Beauty of All Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Sum of Beauty of All Substrings solution in C++
4. Sum of Beauty of All Substrings solution in Java
5. Sum of Beauty of All Substrings solution in Python
6. Additional Resources

Problem Statement of Sum of Beauty of All Substrings

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.

For example, the beauty of “abaacc” is 3 – 1 = 2.

Given a string s, return the sum of beauty of all of its substrings.

Example 1:

Input: s = “aabcb”
Output: 5
Explanation: The substrings with non-zero beauty are [“aab”,”aabc”,”aabcb”,”abcb”,”bcb”], each with beauty equal to 1.
Example 2:

Input: s = “aabcbaa”
Output: 17

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters.

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(26) = O(1)

1781. Sum of Beauty of All Substrings LeetCode Solution in C++

class Solution {
 public:
  int beautySum(string s) {
    int ans = 0;

    for (int i = 0; i < s.length(); ++i) {
      vector<int> count(26);
      for (int j = i; j < s.length(); ++j) {
        ++count[s[j] - 'a'];
        ans += ranges::max(count) - getMinFreq(count);
      }
    }

    return ans;
  }

 private:
  // Returns the minimum frequency > 0.
  int getMinFreq(const vector<int>& count) {
    int minFreq = INT_MAX;
    for (const int freq : count)
      if (freq > 0)
        minFreq = min(minFreq, freq);
    return minFreq;
  }
};
/* code provided by PROGIEZ */

1781. Sum of Beauty of All Substrings LeetCode Solution in Java

class Solution {
  public int beautySum(String s) {
    int ans = 0;

    for (int i = 0; i < s.length(); ++i) {
      int[] count = new int[26];
      for (int j = i; j < s.length(); ++j) {
        ++count[s.charAt(j) - 'a'];
        ans += Arrays.stream(count).max().getAsInt() - getMinFreq(count);
      }
    }

    return ans;
  }

  // Returns the minimum frequency > 0.
  private int getMin(int[] count) {
    int minFreq = Integer.MAX_VALUE;
    for (final int freq : count)
      if (freq > 0)
        minFreq = min(minFreq, freq);
    return minFreq;
  }
}
// code provided by PROGIEZ

1781. Sum of Beauty of All Substrings LeetCode Solution in Python

class Solution:
  def beautySum(self, s: str) -> int:
    ans = 0

    for i in range(len(s)):
      count = collections.Counter()
      for j in range(i, len(s)):
        count[s[j]] += 1
        ans += max(count.values()) - min(count.values())

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.