这是一道 LeetCode 第 2842 题（"统计一个字符串的 k 子序列美丽值最大的数目"）的 Java 实现。

题目理解

我们需要在字符串中找出所有长度为 k 的子序列，这些子序列的美丽值最大。美丽值定义为子序列中不同字母的个数。

具体来说：

1. 找出所有长度为 k 的子序列中，不同字母的最大个数
2. 统计美丽值等于这个最大值的子序列个数
3. 结果对 10^9 + 7 取模

解题思路

1. 统计每个字母出现的频率
2. 按频率降序排序
3. 找到最大美丽值：从频率最高的字母开始选，直到凑够 k 个
4. 关键点：可能多个字母有相同频率，需要组合计算

Java 实现

```java
import java.util.*;

class Solution {
    private static final int MOD = 1_000_000_007;
    
    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        // 统计每个字母出现的频率
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        
        // 过滤掉频率为0的字母，并按频率降序排序
        List<Integer> frequencies = new ArrayList<>();
        for (int f : freq) {
            if (f > 0) {
                frequencies.add(f);
            }
        }
        frequencies.sort((a, b) -> b - a);
        
        // 如果字母种类少于k，无法组成k长度的子序列
        if (frequencies.size() < k) {
            return 0;
        }
        
        // 确定最大美丽值对应的频率分布
        // 第k个频率值（0-indexed）
        int threshold = frequencies.get(k - 1);
        
        // 统计频率大于threshold的字母个数
        int greaterCount = 0;
        int equalCount = 0;
        for (int f : frequencies) {
            if (f > threshold) {
                greaterCount++;
            } else if (f == threshold) {
                equalCount++;
            }
        }
        
        // 必须从equalCount个频率为threshold的字母中选择
        // 需要选择的threshold字母个数 = k - greaterCount
        int needFromEqual = k - greaterCount;
        
        // 如果needFromEqual不在有效范围内，返回0
        if (needFromEqual < 0 || needFromEqual > equalCount) {
            return 0;
        }
        
        // 计算组合数 C(equalCount, needFromEqual)
        long combinations = comb(equalCount, needFromEqual);
        
        // 计算每个threshold字母的贡献: threshold的needFromEqual次方
        long contribution = pow(threshold, needFromEqual);
        
        // 最终结果 = 组合数 * 贡献 mod MOD
        long result = combinations % MOD * contribution % MOD;
        
        // 乘以所有大于threshold字母的频率（它们必须被选）
        // 实际上大于threshold的每个字母都有1种选择方式（必须选）
        // 但我们需要乘以它们的频率乘积，因为每个字母的任意一个出现位置都可以被选
        // 实际上题目要求的是子序列的个数，不是字母的组合数
        // 让我重新思考...
        
        return (int) result;
    }
    
    // 计算组合数 C(n, m) mod MOD
    private long comb(int n, int m) {
        if (m < 0 || m > n) return 0;
        if (m == 0 || m == n) return 1;
        
        // 使用阶乘和逆元计算
        long[] fact = new long[n + 1];
        long[] invFact = new long[n + 1];
        
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        
        invFact[n] = pow(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % MOD;
        }
        
        return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
    }
    
    // 快速幂
    private long pow(long base, long exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result * base % MOD;
            }
            base = base * base % MOD;
            exp >>= 1;
        }
        return result;
    }
}
```

修正版本

上面的实现有个问题：对于频率大于 threshold 的字母，每个字母的每个出现位置都可以被选择。我们需要正确计算子序列的个数。

```java
import java.util.*;

class Solution {
    private static final int MOD = 1_000_000_007;
    
    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        // 统计频率
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        
        // 收集非零频率并排序
        List<Integer> freqs = new ArrayList<>();
        for (int f : freq) {
            if (f > 0) {
                freqs.add(f);
            }
        }
        
        // 检查是否能组成k长度的子序列
        if (freqs.size() < k) {
            return 0;
        }
        
        // 降序排序
        freqs.sort((a, b) -> b - a);
        
        // 找到第k大的频率
        int targetFreq = freqs.get(k - 1);
        
        // 统计大于targetFreq和等于targetFreq的数量
        int greater = 0;
        int equal = 0;
        for (int f : freqs) {
            if (f > targetFreq) greater++;
            else if (f == targetFreq) equal++;
        }
        
        // 需要从相等频率中选择的数量
        int needFromEqual = k - greater;
        
        // 计算组合数
        long comb = nCk(equal, needFromEqual);
        
        // 对于每个被选中的频率，该字母的所有位置都可以选择
        // 但是不同的字母组合会产生不同的子序列
        
        // 结果 = 组合数 * (targetFreq)^needFromEqual 
        // 再乘以所有大于targetFreq的频率（这些必须被选）
        long result = comb % MOD;
        result = result * pow(targetFreq, needFromEqual) % MOD;
        
        for (int f : freqs) {
            if (f > targetFreq) {
                result = result * f % MOD;
            }
        }
        
        return (int) result;
    }
    
    // 组合数计算 C(n, m)
    private long nCk(int n, int m) {
        if (m < 0 || m > n) return 0;
        if (m == 0 || m == n) return 1;
        
        long numerator = 1;
        long denominator = 1;
        
        // 使用乘法逆元
        m = Math.min(m, n - m);
        
        for (int i = 0; i < m; i++) {
            numerator = numerator * (n - i) % MOD;
            denominator = denominator * (i + 1) % MOD;
        }
        
        return numerator * pow(denominator, MOD - 2) % MOD;
    }
    
    private long pow(long a, long b) {
        long result = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) {
                result = result * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return result;
    }
}
```

算法复杂度

· 时间复杂度: O(n + 26 log 26)，其中 n 是字符串长度
· 空间复杂度: O(1)

核心要点

1. 美丽值最大化的策略：选择频率最高的 k 个不同字母
2. 组合计算：当多个字母频率相同时，需要从中选择部分
3. 子序列计数：每个被选中的字母，可以从它的所有出现位置中任选一个
4. 取模运算：结果对 10^9+7 取模

这个解法能够正确计算出美丽值最大的 k 子序列的个数。