这是 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('');
};
```
复杂度分析：
- 时间：`O(26 × m × 26)`，其中 `m = ⌊n/2⌋ ≤ 5000`。每次 `countPermutations` 遍历 26 个字母，试填最多 26 × m 次。
- 空间：`O(1)`，仅使用固定大小的频率数组。
