当前位置：首页 > news >正文

DeepSeek LeetCode 2842. 统计一个字符串的 k 子序列美丽值最大的数目 Java实现

news 2026/5/30 13:30:35

这是一道 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;
}
}
```