题目描述

一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

比方说，"abaacc" 的美丽值为 3 - 1 = 2。
给你一个字符串 s，请你返回它所有子字符串的 美丽值 之和。

样例

输入：s = "aabcb"
输出：5
解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"]，每一个字符串的美丽值都为 1。

输入：s = "aabcbaa"
输出：17

限制

• 1 <= s.length <= 500
• s 只包含小写英文字母。

算法

(暴力枚举) $O(n^2)$

1. 枚举所有子串，枚举过程中，更新子串所有 26 个字符的出现次数。
2. 每个子串遍历所有 26 个字符求出最大和最小值只差。

时间复杂度

• 共有 $O(n^2)$ 个子串，每个子串仅需要常数的时间更新和判断。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    int calc(const vector<int> &s) {
        int ma = INT_MIN, mi = INT_MAX;
        for (int i = 0; i < 26; i++) {
            if (s[i] == 0)
                continue;
            ma = max(ma, s[i]);
            mi = min(mi, s[i]);
        }
        return ma - mi;
    }

public:
    int beautySum(string s) {
        const int n = s.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            vector<int> fre(26, 0);
            for (int j = i; j < n; j++) {
                fre[s[j] - 'a']++;
                ans += calc(fre);
            }
        }
        return ans;
    }
};