花花酱 LeetCode 1781. Sum of Beauty of All Substrings

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

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:

Solution: Treemap

Time complexity: O(n²log26)
Space complexity: O(26)

// Author: Huahua

class Solution {

public:

int beautySum(string_view s) {

const int n = s.size();

int ans = 0;

vector<int> f(26);

map<int, int> m;

for (int i = 0; i < n; ++i) {

fill(begin(f), end(f), 0);

m.clear();

for (int j = i; j < n; ++j) {

const int c = ++f[s[j] - 'a'];

++m[c];

if (c > 1) {

auto it = m.find(c - 1);

if (--it->second == 0)

m.erase(it);

}

ans += rbegin(m)->first - begin(m)->first;

}

return ans;

}

};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏