Sum of Beauty of All Substrings — LeetCode 1781 Python Solution

The problem

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.

Example

Input

s = "aabcb"

Output

5

Explanation

The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.

Python solution

class Solution:
    def beautySum(self, s: str) -> int:
        ans, n = 0, len(s)
        for i in range(n):
            cnt = Counter()
            for j in range(i, n):
                cnt[s[j]] += 1
                ans += max(cnt.values()) - min(cnt.values())
        return ans

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1781. Sum of Beauty of All Substrings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems