力扣2842题解：统计美丽值最大的k子序列数目

4天前力扣题解60

一、问题理解

题目要求我们找到所有长度为k的子序列中，美丽值最大的那些子序列的数量。美丽值定义为子序列中每个字符在整个字符串中出现次数的总和。

关键点：

子序列：可以不连续但顺序要保持
美丽值计算：基于原字符串中的字符频率
结果要对10^9+7取模

二、解题思路

‌第一步：统计字符频率‌
我们需要先统计每个字符在字符串中出现的次数，这决定了每个字符对美丽值的贡献。

‌第二步：检查可行性‌
如果字符串中不同字符的数量小于k，那么不可能构造出满足条件的子序列，直接返回0。

‌第三步：排序频率‌
为了得到最大的美丽值，我们应该选择出现频率最高的k个字符。因此需要将频率从高到低排序。

‌第四步：计算美丽值‌
前k个最高频率的和就是最大美丽值。

‌第五步：计算子序列数量‌
这里需要考虑两种情况：

前k个频率都不同：数量就是这些频率的乘积
有相同频率的字符：需要计算组合数

三、组合数学的应用

当有多个字符具有相同的频率时，我们需要计算从这些字符中选择指定数量的组合方式。例如，如果有5个字符频率都是3，我们需要从中选择2个，那么组合数是C(5,2)=10。

四、代码实现细节

class Solution {
public:
    int countKSubsequencesWithMaxBeauty(string s, int k) {
        const int MOD = 1e9 + 7;
        
        // 统计每个字符的出现频率
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        // 如果不同字符数小于k，不可能有k子序列，返回0
        if (freq.size() < k) {
            return 0;
        }
        
        // 将频率从高到低排序
        vector<int> counts;
        for (auto& [c, cnt] : freq) {
            counts.push_back(cnt);
        }
        sort(counts.rbegin(), counts.rend());
        
        long long res = 1;
        int last = -1;
        int same_count = 0;
        
        for (int i = 0; i < k; ++i) {
            res = (res * counts[i]) % MOD;
            
            // 统计有多少个字符的频率等于当前处理的频率
            if (counts[i] == last) {
                same_count++;
            } else {
                last = counts[i];
                same_count = 1;
            }
        }
        
        // 处理相同频率的情况
        int total_same = 0;
        for (int cnt : counts) {
            if (cnt == last) {
                total_same++;
            }
        }
        
        // 计算组合数 C(total_same, same_count)
        long long comb = 1;
        for (int i = 1; i <= same_count; ++i) {
            comb = comb * (total_same - same_count + i) / i;
        }
        
        res = (res * comb) % MOD;
        
        return res;
    }
};