企业官网建设流程全解析

这是 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"`