DeepSeek LeetCode 2842. 统计一个字符串的 k 子序列美丽值最大的数目 TypeScript实现
这是 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];
}
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
/**
* 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 实现类型安全、性能优良，能够正确解决原题。