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

Kimi LeetCode 3518. 最小回文排列 II JavaScript实现

news 2026/7/9 8:32:22

这是 LeetCode 3518「最小回文排列 II」的 JavaScript 实现。

核心思路：
1. 回文串由左半部分唯一决定（奇数长度时中间字符固定）
2. 将问题转化为求左半部分字符的第 k 小字典序排列
3. 使用试填法：从左到右枚举每个位置，按 `'a'` 到 `'z'` 尝试。若当前字符填入后，剩余位置的排列数 ≥ k，则确定该字符；否则 k 减去该排列数，继续尝试下一个字符。
4. 由于 `k ≤ 10^6`，计算排列数时设置上限 `k+1` 进行截断，避免大数溢出。

```javascript
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var smallestPalindrome = function(s, k) {
const LIMIT = k + 1; // 排列数上限，超过即截断
const freq = new Array(26).fill(0);

// 统计字符频率
for (const ch of s) {
freq[ch.charCodeAt(0) - 97]++;
}

// 确定中间字符（出现奇数次的唯一字符）
let mid = '';
for (let i = 0; i < 26; i++) {
if (freq[i] % 2 === 1) {
mid = String.fromCharCode(i + 97);
freq[i]--;
break;
}
}

// 左半部分字符频率（原频率折半）
const half = new Array(26).fill(0);
let m = 0; // 左半部分长度
for (let i = 0; i < 26; i++) {
half[i] = freq[i] / 2;
m += half[i];
}

// 计算组合数 C(n, m)，超过 limit 则截断
function comb(n, m, limit) {
m = Math.min(m, n - m);
let res = 1;
for (let i = 1; i <= m; i++) {
res = res * (n - i + 1) / i;
if (res >= limit) return limit;
}
return Math.floor(res);
}

// 计算多重集排列数：n! / (c0! * c1! * ... * c25!)
// 转化为连乘组合数：C(n,c0) * C(n-c0,c1) * ...
function countPermutations(cnt) {
let total = 1;
let n = 0;
for (let c of cnt) n += c;

for (let i = 0; i < 26; i++) {
if (cnt[i] === 0) continue;
total *= comb(n, cnt[i], LIMIT);
if (total >= LIMIT) return LIMIT;
n -= cnt[i];
}
return total;
}

// 如果总排列数不足 k，返回空串
if (countPermutations(half) < k) return '';

// 试填法构造左半部分
let left = '';
for (let pos = 0; pos < m; pos++) {
for (let i = 0; i < 26; i++) {
if (half[i] === 0) continue;

half[i]--; // 尝试放入字符 i
const perm = countPermutations(half);

if (perm >= k) {
// 第 k 个排列在当前分支中
left += String.fromCharCode(i + 97);
break;
} else {
// 跳过当前分支的所有排列
k -= perm;
half[i]++; // 恢复
}
}
}

// 左半 + 中间 + 左半反转
return left + mid + left.split('').reverse().join('');
};
```