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

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

news 2026/6/13 9:45:32

这是 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 实现类型安全、性能优良，能够正确解决原题。

http://www.gsyq.cn/news/1427203.html

相关文章：

  • 深圳装修后甲醛超标不用慌 科学除甲醛实用指南 - 环保除醛知识库
  • 大众点评爬虫终极指南：15分钟破解动态字体加密，轻松采集全站数据
  • SAP Cloud ERP 是什么，一篇文章讲清楚
  • 南京乐意工程机械租赁：专业的南京升降车租赁公司 - LYL仔仔
  • 万宁CMA甲醛检测公司哪家好？海南宏启环境，本地口碑榜首，精准靠谱 - 专注室内空气检测治理
  • 咪头选型与声腔结构匹配性问题的系统解决方案 - 麦可兴mic10
  • Windows Server 2019上玩转PXE：手把手教你用MDT定制专属WinPE启动盘（含资源下载）
  • 买包易闲置难处理，走访西安本地包包回收行业实情 - 合扬奢侈品交易中心
  • 2026精选：喷淋塔/pph喷淋塔/pp喷淋塔厂家推荐榜单：助力企业环保达标 - 资讯快报
  • 告别单调！用自定义TabBar为你的小程序打造沉浸式页面体验（附动态隐藏方案）
  • 保姆级教程：在Ubuntu 22.04上为新唐NUC980编译5.10.y内核与根文件系统（含SD卡分区避坑指南）
  • 2026盐城卫生间阳台漏水维修市场价 靠谱防水品牌排名（本地适配版） - 国麟测评
  • Python之rkstiff包语法、参数和实际应用案例
  • 四川舞蹈表演专业院校推荐，2026艺考择校看这篇就够 - 品牌2025
  • iOS 15+免越狱深度定制完全指南：CowabungaLite让你的iPhone与众不同
  • Meta开源LLaMA与AI社交融合战略：应对ChatGPT挑战的生态博弈
  • ULINK2调试器VCC跳线设置与JTAG供电原理详解
  • 保姆级教程：在Firefly RK3566开发板上用GStreamer同时预览两个MIPI摄像头画面
  • Python之rktools包语法、参数和实际应用案例
  • LizzieYzy：免费开源围棋AI分析工具，打造你的专业围棋教练
  • DAO实战指南：区块链与AI如何重塑组织协作与治理
  • AI如何颠覆网络安全：从规则响应到智能预测的范式转移
  • ToDesk Linux客户端安装后，临时密码总变？手把手教你解读config.ini配置文件
  • SWAT建模效率翻倍：HWSD土壤数据处理全流程自动化脚本思路分享（Python+ArcPy）
  • 数据泄露、越狱攻击、幻觉放大…Claude三大致命风险全解析，今天不看明天踩坑
  • 7th grade math （2026.05.30）
  • Python之rl4grid包语法、参数和实际应用案例
  • 2023年加密货币入门：10美元实战指南与安全投资框架
  • ARMv8.1-A架构LORegion机制详解与优化实践
  • SpringBoot项目实战：用EasyPoi + Docx4j搞定Word模板转PDF（含图片和字体乱码解决方案）