1781. Sum of Beauty of All Substrings
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"
is3 - 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.
Solutions
Solution 1: Enumeration + Counting
Enumerate the starting position $i$ of each substring, find all substrings with the character at this starting position as the left endpoint, then calculate the beauty value of each substring, and accumulate it to the answer.
The time complexity is $O(n^2 \times C)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string, and $C$ is the size of the character set. In this problem, $C = 26$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|