这是 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 代码javaclass 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) — 仅使用固定大小的数组和变量。---示例验证输入 过程 输出sabba, k2 左半 ab总排列 2 种。第 1 位试填 a 得 1 种 2跳过试填 b 得 1 种 1选 b第 2 位只能 a。 baabsaa, k2 左半 a总排列 1 种 2。 sbacab, k1 左半 ba总排列 2 种。第 1 位试填 a 得 1 种 1选 a第 2 位只能 b。中间 c。 abcba
