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` 的上限，既防溢出又不会影响正确判断。