C++解决LeetCode1781：所有子字符串的美丽值总和

LeetCode 1781：所有子字符串的美丽值总和

题目链接：LeetCode 1781

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

• 例如，字符串 "abaacc" 的美丽值为 3 - 1 = 2。

给定一个字符串 s，任务是计算并返回其所有子字符串的美丽值之和。

示例

示例 1

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

示例 2

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

提示

• 字符串长度范围为 1 到 500。


• 字符串仅由小写字母组成。

解决方案

方法一：利用前缀和

此方法首先构建一个二维数组来存储每个字符在不同位置的累积计数。通过这种方式，可以在后续计算任意子字符串时快速获取字符的最大和最小出现频率，从而计算美丽值。

class Solution {
public:
    int beautySum(string s) {
        int n = s.size();
        vector> prefix(26, vector(n + 1));
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <26; c++) {
                prefix[c][i] = prefix[c][i - 1];
            }
            prefix[s[i - 1] - 'a'][i]++;
        }
        int ans = 0;
        for (int i = 0; i             for (int j = i + 1; j                 int M = 0, m = 1000;
                for (int c = 0; c <26; c++) {
                    int thisC = prefix[c][j + 1] - prefix[c][i];
                    M = max(M, thisC);
                    if (thisC) {
                        m = min(m, thisC);
                    }
                }
                ans += M - m;
            }
        }
        return ans;
    }
};

方法二：动态计算

这种方法避免了预先计算前缀和，而是随着遍历过程动态更新字符的出现频率。这种方法减少了额外的空间需求，同时保持了算法的时间效率。

class Solution {
public:
    int beautySum(string s) {
        int ans = 0;
        int n = s.size();
        for (int i = 0; i             int cnt[26] = {0};
            for (int j = i; j                 cnt[s[j] - 'a']++;
                int M = 0, m = 1000;
                for (int d = 0; d <26; d++) {
                    M = max(M, cnt[d]);
                    if (cnt[d])
                        m = min(m, cnt[d]);
                }
                ans += M - m;
            }
        }
        return ans;
    }
};