Kimi LeetCode 3518. 最小回文排列 II Python3实现

```python
class Solution:
MAX_K = 1_000_001

def smallestPalindrome(self, s: str, k: int) -> str:
n = len(s)
half = s[:n // 2]
mid = s[n // 2] if n % 2 == 1 else ""

cnt = [0] * 26
for c in half:
cnt[ord(c) - ord('a')] += 1

# 总排列数不足 k
if self.count_arrangements(cnt) < k:
return ""

half_len = len(half)
ans = []

for _ in range(half_len):
for i in range(26):
if cnt[i] == 0:
continue
# 尝试将字符 i 填入当前位
cnt[i] -= 1
ways = self.count_arrangements(cnt)
if k <= ways:
ans.append(chr(ord('a') + i))
break
else:
# 该分支不包含目标，恢复并跳过
cnt[i] += 1
k -= ways

left = "".join(ans)
return left + mid + left[::-1]

def count_arrangements(self, cnt: list[int]) -> int:
"""计算多重集排列数，超过 MAX_K 时截断"""
total = sum(cnt)
res = 1
for c in cnt:
if c == 0:
continue
res *= self.comb(total, c)
if res >= self.MAX_K:
return self.MAX_K
total -= c
return res

def comb(self, n: int, k: int) -> int:
"""组合数 C(n, k)，超过 MAX_K 时截断"""
k = min(k, n - k)
res = 1
for i in range(1, k + 1):
res = res * (n - i + 1) // i
if res >= self.MAX_K:
return self.MAX_K
return res
```

核心思路

回文串由左半部分唯一确定（奇数长度时中间字符固定），因此问题转化为求左半部分字符串的第 k 小不同排列。

1. 多重集排列数：用组合数连乘 `C(n, v1) * C(n-v1, v2) * ...` 计算，避免阶乘溢出。由于 `k ≤ 10^6`，乘积超过 `1_000_001` 时直接截断。
2. 贪心构造：从左到右逐位确定，从小到大枚举 `'a'~'z'`，尝试将当前字符填入该位，计算剩余位置的排列数 `ways`。若 `k ≤ ways`，则确定该位；否则 `k -= ways` 并尝试下一个字符。
3. 复杂度：时间 `O(|half| * 26 * log(k))`，空间 `O(1)`。