pythonclass Solution:MAX_K 1_000_001def 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] * 26for c in half:cnt[ord(c) - ord(a)] 1# 总排列数不足 kif 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] - 1ways self.count_arrangements(cnt)if k ways:ans.append(chr(ord(a) i))breakelse:# 该分支不包含目标恢复并跳过cnt[i] 1k - waysleft .join(ans)return left mid left[::-1]def count_arrangements(self, cnt: list[int]) - int:计算多重集排列数超过 MAX_K 时截断total sum(cnt)res 1for c in cnt:if c 0:continueres * self.comb(total, c)if res self.MAX_K:return self.MAX_Ktotal - creturn resdef comb(self, n: int, k: int) - int:组合数 C(n, k)超过 MAX_K 时截断k min(k, n - k)res 1for i in range(1, k 1):res res * (n - i 1) // iif res self.MAX_K:return self.MAX_Kreturn 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)。