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)。rustimpl 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 - ba) as usize] 1;}// 总排列数不足 kif 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;}// 尝试填入字符 icnt[i] - 1;let ways Self::count_arrangements(cnt);if k ways {ans.push((ba 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-k1) / k 递推并取 k min(k, n-k) 减少循环次数同时保证中间结果始终可被整除。- 截断值 MAX_K 1_000_001 略大于题目 k 的上限既防溢出又不会影响正确判断。