Skip to content

1781. Sum of Beauty of All Substrings

Difficulty Topics

Description

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.

Solution

sum-of-beauty-of-all-substrings.py
class Solution:
    def beautySum(self, s: str) -> int:
        n = len(s)
        res = 0

        for i in range(n):
            mp = collections.defaultdict(int)
            for j in range(i, n):
                mp[s[j]] += 1
                v = mp.values()
                res += max(v) - min(v)

        return res