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

这是 LeetCode 2842 题统计一个字符串的 k 子序列美丽值最大的数目的 JavaScript 实现。解题思路1. 统计频率统计每个字母的出现次数2. 排序按频率降序排序3. 确定目标频率找到第 k 大的频率值4. 分类统计· 频率大于目标值的字母必须选· 频率等于目标值的字母需要选一部分5. 组合计算用组合数学计算子序列个数JavaScript 实现javascript/*** param {string} s* param {number} k* return {number}*/var countKSubsequencesWithMaxBeauty function(s, k) {const MOD BigInt(1000000007);// 1. 统计每个字母的频率const freq new Array(26).fill(0);for (const char of s) {freq[char.charCodeAt(0) - 97];}// 2. 过滤掉频率为0的字母并降序排序const frequencies freq.filter(f f 0).sort((a, b) b - a);// 3. 如果字母种类不足k个无法组成k长度的子序列if (frequencies.length k) {return 0;}// 4. 找到第k大的频率0-indexedconst targetFreq frequencies[k - 1];// 5. 统计大于targetFreq和等于targetFreq的个数let greaterCount 0;let equalCount 0;for (const f of frequencies) {if (f targetFreq) {greaterCount;} else if (f targetFreq) {equalCount;}}// 6. 需要从equalCount中选取的数量const needFromEqual k - greaterCount;// 7. 检查合法性if (needFromEqual 0 || needFromEqual equalCount) {return 0;}// 8. 计算组合数 C(equalCount, needFromEqual)const combinations nCk(equalCount, needFromEqual, MOD);// 9. 计算贡献targetFreq 的 needFromEqual 次方let contribution 1n;for (let i 0; i needFromEqual; i) {contribution (contribution * BigInt(targetFreq)) % MOD;}// 10. 计算最终结果let result (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 {number} n* param {number} m* param {bigint} MOD* returns {bigint}*/function nCk(n, m, MOD) {if (m 0 || m n) return 0n;if (m 0 || m n) return 1n;// 使用更小的m进行计算m Math.min(m, n - m);let numerator 1n;let denominator 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 {bigint} base* param {bigint} exponent* param {bigint} mod* returns {bigint}*/function modPow(base, exponent, mod) {let result 1n;base base % mod;let exp exponent;while (exp 0) {if (exp 1n) {result (result * base) % mod;}base (base * base) % mod;exp 1n;}return result;}更简洁的版本使用数学库特性javascriptvar countKSubsequencesWithMaxBeauty function(s, k) {const MOD 1000000007n;// 统计频率并降序排序const freq new Array(26).fill(0);for (const c of s) freq[c.charCodeAt(0) - 97];const freqs freq.filter(f f 0).sort((a, b) b - a);if (freqs.length k) return 0;const target freqs[k - 1];// 统计大于和等于target的数量let greater 0, equal 0;for (const f of freqs) {if (f target) greater;else if (f target) equal;}const need k - greater;if (need 0 || need equal) return 0;// 计算组合数 C(equal, need)const comb (n, m) {if (m 0 || m n) return 1n;m Math.min(m, n - m);let num 1n, den 1n;for (let i 0; i m; i) {num num * BigInt(n - i) % MOD;den den * BigInt(i 1) % MOD;}// 使用快速幂计算逆元const inv (a, p) {let res 1n;while (p 0) {if (p 1n) res res * a % MOD;a a * a % MOD;p 1n;}return res;};return num * inv(den, MOD - 2n) % MOD;};let result comb(equal, need);// 乘以target^needfor (let i 0; i need; i) {result result * BigInt(target) % MOD;}// 乘以所有大于target的频率for (const f of freqs) {if (f target) {result result * BigInt(f) % MOD;}}return Number(result);};测试示例javascript// 示例1console.log(countKSubsequencesWithMaxBeauty(bcca, 2)); // 预期输出: 4// 示例2console.log(countKSubsequencesWithMaxBeauty(abbcd, 4)); // 预期输出: 2// 示例3console.log(countKSubsequencesWithMaxBeauty(aabbccdd, 4)); // 预期输出: 16算法复杂度· 时间复杂度: O(n 26 log 26)其中 n 是字符串长度· 空间复杂度: O(1)关键点说明1. BigInt 处理由于结果可能很大且需要取模JavaScript 中使用 BigInt 避免精度丢失2. 组合数计算使用乘法逆元和费马小定理计算组合数3. 快速幂高效计算大数的幂4. 取模运算所有乘法后都要取模 10^97这个实现能够正确计算出所有美丽值最大的 k 子序列的个数。