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

/ 预期: 0 (字母不足)console.log(countKSubsequencesWithMaxBeauty("aabbccdd", 4));// Step 9: 计算贡献值 (targetFreqValue ^ needFromEqual)// Step 8: 计算组合数 C(equalToTarget, needFromEqual)// 8. 计算组合数 C(equalCount, ne

稚辉君.MCA.P9.JAVA

13人浏览 · 2026-05-30 10:43:51

稚辉君.MCA.P9.JAVA · 2026-05-30 10:43:51 发布

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

TypeScript 实现

```typescript
function countKSubsequencesWithMaxBeauty(s: string, k: number): number {
const MOD = 1000000007n;

// 1. 统计每个字母的频率
const freq: number[] = new Array(26).fill(0);
for (const char of s) {
freq[char.charCodeAt(0) - 97]++;
}

// 2. 过滤掉频率为0的字母，并降序排序
const frequencies: number[] = freq.filter(f => f > 0).sort((a, b) => b - a);

// 3. 如果字母种类不足k个，无法组成k长度的子序列
if (frequencies.length < k) {
return 0;
}

// 4. 找到第k大的频率（0-indexed）
const targetFreq: number = frequencies[k - 1];

// 5. 统计大于targetFreq和等于targetFreq的个数
let greaterCount: number = 0;
let equalCount: number = 0;
for (const f of frequencies) {
if (f > targetFreq) {
greaterCount++;
} else if (f === targetFreq) {
equalCount++;
}
}

// 6. 需要从equalCount中选取的数量
const needFromEqual: number = k - greaterCount;

// 7. 检查合法性
if (needFromEqual < 0 || needFromEqual > equalCount) {
return 0;
}

// 8. 计算组合数 C(equalCount, needFromEqual)
const combinations: bigint = nCk(equalCount, needFromEqual, MOD);

// 9. 计算贡献：targetFreq 的 needFromEqual 次方
let contribution: bigint = 1n;
for (let i = 0; i < needFromEqual; i++) {
contribution = (contribution * BigInt(targetFreq)) % MOD;
}

// 10. 计算最终结果
let result: bigint = (combinations * contribution) % MOD;

// 11. 乘以所有大于targetFreq的频率
for (const f of frequencies) {
if (f > targetFreq) {
result = (result * BigInt(f)) % MOD;
}
}

return Number(result);
}

/**
* 计算组合数 C(n, m) mod MOD
* @param n - 总数
* @param m - 选取数
* @param MOD - 模数
* @returns 组合数模 MOD 的结果
*/
function nCk(n: number, m: number, MOD: bigint): bigint {
if (m < 0 || m > n) return 0n;
if (m === 0 || m === n) return 1n;

// 使用更小的 m 进行计算，优化性能
m = Math.min(m, n - m);

let numerator: bigint = 1n;
let denominator: bigint = 1n;

for (let i = 0; i < m; i++) {
numerator = (numerator * BigInt(n - i)) % MOD;
denominator = (denominator * BigInt(i + 1)) % MOD;
}

// 使用费马小定理计算分母的逆元
return numerator * modPow(denominator, MOD - 2n, MOD) % MOD;
}

/**
* 快速幂算法（模运算）
* @param base - 底数
* @param exponent - 指数
* @param mod - 模数
* @returns base^exponent mod mod
*/
function modPow(base: bigint, exponent: bigint, mod: bigint): bigint {
let result: bigint = 1n;
let b: bigint = base % mod;
let exp: bigint = exponent;

while (exp > 0) {
if (exp & 1n) {
result = (result * b) % mod;
}
b = (b * b) % mod;
exp >>= 1n;
}

return result;
}
```

更优化的版本（使用预计算阶乘）

```typescript
function countKSubsequencesWithMaxBeauty(s: string, k: number): number {
const MOD = 1000000007n;

// 统计频率
const freq: number[] = new Array(26).fill(0);
for (const char of s) {
freq[char.charCodeAt(0) - 97]++;
}

// 过滤并排序
const freqs: number[] = freq.filter(f => f > 0).sort((a, b) => b - a);

if (freqs.length < k) return 0;

const target: number = freqs[k - 1];

// 统计大于和等于 target 的数量
let greater: number = 0;
let equal: number = 0;
for (const f of freqs) {
if (f > target) greater++;
else if (f === target) equal++;
}

const need: number = k - greater;
if (need < 0 || need > equal) return 0;

// 使用预计算的阶乘和逆元来计算组合数
const maxN: number = Math.max(equal, 26);
const [fact, invFact] = precomputeFactorials(maxN, MOD);

// 计算组合数 C(equal, need)
const combinations: bigint = fact[equal] * invFact[need] % MOD * invFact[equal - need] % MOD;

// 计算贡献
let result: bigint = combinations;
result = result * modPow(BigInt(target), BigInt(need), MOD) % MOD;

// 乘以所有大于 target 的频率
for (const f of freqs) {
if (f > target) {
result = result * BigInt(f) % MOD;
}
}

return Number(result);
}

/**
* 预计算阶乘和逆元
*/
function precomputeFactorials(maxN: number, MOD: bigint): [bigint[], bigint[]] {
const fact: bigint[] = new Array(maxN + 1);
const invFact: bigint[] = new Array(maxN + 1);

fact[0] = 1n;
for (let i = 1; i <= maxN; i++) {
fact[i] = fact[i - 1] * BigInt(i) % MOD;
}

// 使用费马小定理计算最大阶乘的逆元
invFact[maxN] = modPow(fact[maxN], MOD - 2n, MOD);

// 递推计算其他逆元
for (let i = maxN - 1; i >= 0; i--) {
invFact[i] = invFact[i + 1] * BigInt(i + 1) % MOD;
}

return [fact, invFact];
}

带有详细注释的版本

```typescript
/**
* LeetCode 2842. 统计一个字符串的 k 子序列美丽值最大的数目
* @param s - 输入字符串
* @param k - 子序列长度
* @returns 美丽值最大的 k 子序列的数目（模 10^9+7）
*/
function countKSubsequencesWithMaxBeauty(s: string, k: number): number {
const MOD = 1000000007n;

// Step 1: 统计每个小写字母的出现频率
const frequency: number[] = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
const index: number = s.charCodeAt(i) - 97;
frequency[index]++;
}

// Step 2: 收集所有非零频率并按降序排序
const nonZeroFreqs: number[] = frequency.filter(f => f > 0);
nonZeroFreqs.sort((a, b) => b - a);

// Step 3: 边界检查 - 字母种类不足 k 个
if (nonZeroFreqs.length < k) {
return 0;
}

// Step 4: 找到第 k 大的频率值
const targetFreqValue: number = nonZeroFreqs[k - 1];

// Step 5: 统计大于和等于目标频率的字母数量
let greaterThanTarget: number = 0;
let equalToTarget: number = 0;

for (const f of nonZeroFreqs) {
if (f > targetFreqValue) {
greaterThanTarget++;
} else if (f === targetFreqValue) {
equalToTarget++;
}
}

// Step 6: 需要从频率等于目标值的字母中选择的数量
const needFromEqual: number = k - greaterThanTarget;

// Step 7: 验证选择数量是否合法
if (needFromEqual < 0 || needFromEqual > equalToTarget) {
return 0;
}

// Step 8: 计算组合数 C(equalToTarget, needFromEqual)
const combinations: bigint = calculateCombination(equalToTarget, needFromEqual, MOD);

// Step 9: 计算贡献值 (targetFreqValue ^ needFromEqual)
let contribution: bigint = fastPower(BigInt(targetFreqValue), BigInt(needFromEqual), MOD);

// Step 10: 计算结果 = 组合数 × 贡献值
let result: bigint = (combinations * contribution) % MOD;

// Step 11: 乘以所有大于目标频率的字母的频率值
for (const f of nonZeroFreqs) {
if (f > targetFreqValue) {
result = (result * BigInt(f)) % MOD;
}
}

return Number(result);
}

/**
* 计算组合数 C(n, m) mod MOD
* 使用乘法逆元方法
*/
function calculateCombination(n: number, m: number, MOD: bigint): bigint {
if (m < 0 || m > n) return 0n;
if (m === 0 || m === n) return 1n;

// 优化：使用较小的 m
m = Math.min(m, n - m);

let numerator: bigint = 1n;
let denominator: bigint = 1n;

// 计算分子和分母
for (let i = 0; i < m; i++) {
numerator = (numerator * BigInt(n - i)) % MOD;
denominator = (denominator * BigInt(i + 1)) % MOD;
}

// 返回 numerator * denominator^(-1) mod MOD
return numerator * fastPower(denominator, MOD - 2n, MOD) % MOD;
}

/**
* 快速幂算法（模运算）
* @param base - 底数
* @param exponent - 指数
* @param mod - 模数
* @returns base^exponent mod mod
*/
function fastPower(base: bigint, exponent: bigint, mod: bigint): bigint {
let result: bigint = 1n;
let b: bigint = base % mod;
let e: bigint = exponent;

while (e > 0) {
// 如果当前位是1，乘上当前底数
if (e & 1n) {
result = (result * b) % mod;
}
// 底数平方
b = (b * b) % mod;
// 指数右移一位
e >>= 1n;
}

return result;
}
```

测试用例

```typescript
// 测试示例
console.log(countKSubsequencesWithMaxBeauty("bcca", 2)); // 预期: 4
console.log(countKSubsequencesWithMaxBeauty("abbcd", 4)); // 预期: 2
console.log(countKSubsequencesWithMaxBeauty("aabbccdd", 4)); // 预期: 16

// 更多测试
console.log(countKSubsequencesWithMaxBeauty("abcde", 3)); // 预期: 60
console.log(countKSubsequencesWithMaxBeauty("aaaa", 2)); // 预期: 0 (字母不足)
```

算法复杂度

· 时间复杂度: O(n + 26 log 26) ≈ O(n)
· 空间复杂度: O(1)

类型安全特性

TypeScript 实现充分利用了类型系统：

1. 明确的类型注解：所有函数参数和返回值都有明确类型
2. BigInt 类型：正确处理大整数运算
3. 只读类型：可添加 readonly 修饰符确保数据不被意外修改
4. 元组返回类型：[bigint[], bigint[]] 明确表示返回阶乘和逆元数组

这个 TypeScript 实现类型安全、性能优良，能够正确解决原题。

https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

Claude Opus 4.8 发布：更强编程与更高诚实性

Claude Opus 4.8 发布，带来更强编程能力、更高诚实性，以及动态工作流功能。

AI编程社区

2026年ChatGPT Plus 还值得订阅吗？Plus 和 Pro 有什么区别？

AI编程社区

Skill Creator 不是帮你写一个 SKILL.md，而是把经验变成可复用能力

最近连续做了几轮 OpenClaw、Codex、Claude Code 相关实践后，我越来越觉得：Skill Creator 真正有价值的地方，不是“帮你生成一个技能文件”，而是帮你把一次性的经验，沉淀成可复用、可测试、可迭代的能力。很多人第一次接触 Skill Creator，容易把它理解成：我描述一个需求，它帮我生成一个SKILL.md。这当然是它的一部分价值。但如果只停留在这里，Skill