Kimi LeetCode 3518. 最小回文排列 II Rust实现
LeetCode 3518. 最小回文排列 II 的核心思路是：回文串由前半部分唯一确定（奇数长度时中间字符固定），因此问题转化为求前半部分字符串的第 k 小不同排列。
具体做法：
1. 提取前半部分 `half` 和中间字符 `mid`（若有）。
2. 用组合数连乘计算多重集排列数（避免阶乘溢出）：`C(n, v1) * C(n-v1, v2) * ...`。由于 `k ≤ 10^6`，当乘积超过 `1_000_001` 时直接截断。
3. 若总排列数 `< k`，返回空串。
4. 逐位贪心构造：从小到大枚举 `'a'~'z'`，尝试将当前字符填入该位，计算剩余位置的排列数 `ways`。若 `k ≤ ways`，则确定该位；否则 `k -= ways` 并尝试下一个字符。
5. 最后将构造好的左半部分翻转拼接。
时间复杂度 `O(|half| * 26 * log(k))`，空间复杂度 `O(1)`。
```rust
impl Solution {
const MAX_K: i64 = 1_000_001;
pub fn smallest_palindrome(s: String, k: i32) -> String {
let mut k = k as i64;
let n = s.len();
let half = &s[..n / 2];
let mid = if n % 2 == 0 { "" } else { &s[n / 2..n / 2 + 1] };
let mut cnt = [0i32; 26];
for c in half.chars() {
cnt[(c as u8 - b'a') as usize] += 1;
}
// 总排列数不足 k
if Self::count_arrangements(&cnt) < k {
return String::new();
}
let half_len = half.len();
let mut ans = String::with_capacity(half_len);
for _ in 0..half_len {
for i in 0..26 {
if cnt[i] == 0 {
continue;
}
// 尝试填入字符 i
cnt[i] -= 1;
let ways = Self::count_arrangements(&cnt);
if k <= ways {
ans.push((b'a' + i as u8) as char);
break;
} else {
// 不在该分支，恢复并跳过
cnt[i] += 1;
k -= ways;
}
}
}
let rev: String = ans.chars().rev().collect();
ans + mid + &rev
}
/// 计算多重集排列数，超过 MAX_K 时截断
fn count_arrangements(cnt: &[i32; 26]) -> i64 {
let mut total = 0i32;
for &c in cnt.iter() {
total += c;
}
let mut res: i64 = 1;
for &c in cnt.iter() {
if c == 0 {
continue;
}
res *= Self::comb(total, c);
if res >= Self::MAX_K {
return Self::MAX_K;
}
total -= c;
}
res
}
/// 组合数 C(n, k)，超过 MAX_K 时截断
fn comb(n: i32, k: i32) -> i64 {
let n = n as i64;
let k = k as i64;
let k = k.min(n - k);
let mut res: i64 = 1;
for i in 1..=k {
res = res * (n - i + 1) / i;
if res >= Self::MAX_K {
return Self::MAX_K;
}
}
res
}
}
```
关键点说明：
- `count_arrangements` 将多重集排列分解为依次选位置的组合数连乘，避免了先算大阶乘再除法的溢出问题。
- `comb` 利用 `C(n,k) = C(n,k-1) * (n-k+1) / k` 递推，并取 `k = min(k, n-k)` 减少循环次数，同时保证中间结果始终可被整除。
- 截断值 `MAX_K = 1_000_001` 略大于题目 `k` 的上限，既防溢出又不会影响正确判断。