这是 LeetCode 3518「最小回文排列 II」的 Java 实现，采用试填法 + 组合数学的经典做法。

---

核心思路

回文串由对称的两半决定，只需构造左半部分，右半部分自动确定。

1. 提取左半部分：`s[0..n/2-1]`，中间字符（若长度为奇数）单独记录。
2. 统计左半部分字符频次 `cnt[26]`。
3. 计算总排列数：多重集排列数 = `sz! / (cnt[0]! * cnt[1]! * ... * cnt[25]!)`。若不足 `k`，返回空串。
4. 按位试填：从左到右，每次从小到大尝试字符 `c`：
   - 若当前位放 `c`，则剩余 `sz-i-1` 个位置用剩余字符排列，排列数为 `ways`。
   - 若 `k <= ways`，确定选 `c`；否则 `k -= ways`，尝试下一个字符。

关键优化：用组合数 `C(n,k)` 逐步计算排列数，避免阶乘溢出。一旦超过 `MAX = 10^6 + 1`（因为 `k <= 10^6`）就截断。

---

Java 代码

```java
class Solution {
    private static final int MAX = 1_000_001; // k 最大为 1e6，超过即可截断

    public String smallestPalindrome(String s, int k) {
        int n = s.length();
        int halfLen = n / 2;
        String half = s.substring(0, halfLen);
        char mid = (n % 2 == 1) ? s.charAt(halfLen) : 0;

        // 统计左半部分字符频次
        int[] cnt = new int[26];
        for (char c : half.toCharArray()) {
            cnt[c - 'a']++;
        }

        // 计算总排列数
        long total = countWays(cnt);
        if (total < k) {
            return "";
        }

        StringBuilder left = new StringBuilder();
        long remWays = total; // 剩余排列数

        for (int i = 0; i < halfLen; i++) {
            for (int c = 0; c < 26; c++) {
                if (cnt[c] == 0) continue;

                // 尝试放字符 c，计算以 c 开头的排列数
                cnt[c]--;
                long ways = countWays(cnt);
                cnt[c]++;

                if (k <= ways) {
                    // 第 k 个在以 c 开头的排列中
                    left.append((char) ('a' + c));
                    cnt[c]--;
                    remWays = ways;
                    break;
                } else {
                    // 跳过以 c 开头的所有排列
                    k -= ways;
                }
            }
        }

        // 构造完整回文：左半 + 中间 + 左半反转
        StringBuilder ans = new StringBuilder(left);
        if (mid != 0) ans.append(mid);
        ans.append(left.reverse());

        return ans.toString();
    }

    /**
     * 计算多重集排列数：n! / (cnt[0]! * cnt[1]! * ... * cnt[25]!)
     * 用组合数逐步计算，超过 MAX 则截断
     */
    private long countWays(int[] cnt) {
        int space = 0;
        for (int v : cnt) space += v;

        long ways = 1;
        for (int v : cnt) {
            if (v == 0) continue;
            ways *= comb(space, v);
            if (ways >= MAX) return MAX;
            space -= v;
        }
        return ways;
    }

    /**
     * 计算组合数 C(n,k)，超过 MAX 则截断
     * 利用 C(n,k) = C(n,n-k) 取较小值
     * 分子递减、分母递增，保证整除
     */
    private long comb(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1;
        k = Math.min(k, n - k);

        long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (n - i + 1) / i;
            if (res >= MAX) return MAX;
        }
        return res;
    }
}
```

---

关键点说明

要点    说明    
只构造左半    回文串对称，右半 = 左半反转，中间字符单独处理。    
组合数防溢出    `C(n,k)` 用分子递减、分母递增的方式计算，保证中间结果始终整除，且一旦 `>= MAX` 立即截断。    
多重集排列    将 `n! / (v1! * v2! * ...)` 拆分为 `C(n,v1) * C(n-v1,v2) * ...`，避免大数运算。    
试填法    每次从小到大枚举字符，计算以该字符开头的排列数，用 `k` 与 `ways` 比较确定选择。    
MAX 截断    `k <= 10^6`，排列数超过 `MAX` 后无需精确值，直接返回 `MAX` 即可正确比较。    

---

复杂度分析

指标    复杂度    
时间    `O(n * 26 * log(MAX))` — 最多 `n/2` 位，每位枚举 26 个字符，每次 `countWays` 调用 `O(26 * log(MAX))`。    
空间    `O(1)` — 仅使用固定大小的数组和变量。    

---

示例验证

输入    过程    输出    
`s="abba", k=2`    左半 `"ab"`，总排列 2 种。第 1 位试填 `'a'` 得 1 种 < 2，跳过；试填 `'b'` 得 1 种 >= 1，选 `'b'`；第 2 位只能 `'a'`。    `"baab"`    
`s="aa", k=2`    左半 `"a"`，总排列 1 种 < 2。    `""`    
`s="bacab", k=1`    左半 `"ba"`，总排列 2 种。第 1 位试填 `'a'` 得 1 种 >= 1，选 `'a'`；第 2 位只能 `'b'`。中间 `'c'`。    `"abcba"`