1781.所有子字符串美丽值之和

链接：1781.所有子字符串美丽值之和
难度：Medium
标签：哈希表、字符串、计数
简介：给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。

题解 1 - cpp

• 编辑时间：2022-12-12
• 执行用时：372ms
• 内存消耗：34.7MB
• 编程语言：cpp
• 解法介绍：暴力枚举。

class Solution {
public:
    int beautySum(string s) {
        int ans = 0, n = s.size(), dp[505][505][26] = {0};
        for (int i = 0; i < n; i++) {
            dp[i][i][s[i] - 'a'] = 1;
            for (int j = i - 1; j >= 0; j--) {
                for (int k = 0; k < 26; k++) dp[i][j][k] = dp[i][j + 1][k];
                dp[i][j][s[j] - 'a']++;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int nmin = 500, nmax = 0;
                for (int k = 0; k < 26; k++) {
                    if (dp[i][j][k] == 0) continue;
                    nmin = min(nmin, dp[i][j][k]);
                    nmax = max(nmax, dp[i][j][k]);
                }
                // cout << "j = " << j << ", i = " << i << ", min = " << nmin << ", max = " << nmax << endl;
                ans += nmax - nmin;
            }
        }
        return ans;
    }
};