LeetCode 题解工作台
最小回文排列 I
给你一个 回文 字符串 s 。 返回 s 的按字典序排列的 最小 回文排列。 如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个 回文 字符串。 排列 是字符串中所有字符的重排。 如果字符串 a 按字典序小于字符串 b ，则表示在第一个不同的位置， a 中的字符比 b 中的对应字符在字母…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · string·结合·排序
答案摘要
我们首先统计字符串中每个字符的出现次数，记录在哈希表或数组 中。由于字符串是回文字符串，因此每个字符的出现次数要么是偶数次，要么有且仅有一个字符出现奇数次。 接下来，我们从字典序最小的字符开始，依次将每个字符的一半次数添加到结果字符串的前半部分 中。如果某个字符出现了奇数次，我们将该字符记录为中间字符 。最后，我们将 、 和 的反转拼接起来，得到最终的按字典序排列的最小回文排列。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·排序 题型思路
题目描述
给你一个 回文 字符串 s。
返回 s 的按字典序排列的 最小 回文排列。
如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个 回文 字符串。
排列 是字符串中所有字符的重排。
如果字符串a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。如果在前
min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。
示例 1：
输入： s = "z"
输出： "z"
解释：
仅由一个字符组成的字符串已经是按字典序最小的回文。
示例 2：
输入： s = "babab"
输出： "abbba"
解释：
通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。
示例 3：
输入： s = "daccad"
输出： "acddca"
解释：
通过重排 "daccad" → "acddca"，可以得到按字典序最小的回文。
提示：
1 <= s.length <= 105s由小写英文字母组成。- 保证
s是回文字符串。
解题思路
方法一：计数
我们首先统计字符串中每个字符的出现次数，记录在哈希表或数组 中。由于字符串是回文字符串，因此每个字符的出现次数要么是偶数次，要么有且仅有一个字符出现奇数次。
接下来，我们从字典序最小的字符开始，依次将每个字符的一半次数添加到结果字符串的前半部分 中。如果某个字符出现了奇数次，我们将该字符记录为中间字符 。最后，我们将 、 和 的反转拼接起来，得到最终的按字典序排列的最小回文排列。
时间复杂度 ，其中 是字符串的长度。空间复杂度 ，其中 是字符集的大小，本题中 。
class Solution:
def smallestPalindrome(self, s: str) -> str:
cnt = Counter(s)
t = []
ch = ""
for c in ascii_lowercase:
v = cnt[c] // 2
t.append(c * v)
cnt[c] -= v * 2
if cnt[c] == 1:
ch = c
ans = "".join(t)
ans = ans + ch + ans[::-1]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They hint that a palindrome can be viewed as two mirrored halves plus maybe one center character.
- question_mark
They care whether you know lexicographic order is decided by the earliest position, so the left half must be minimized first.
- question_mark
They want a counting-based construction, not brute-force permutation generation or repeated string resorting.
常见陷阱
外企场景- error
Using all occurrences in sorted order without splitting pairs, which breaks the palindrome structure.
- error
Choosing the middle character incorrectly when one frequency is odd, especially if you treat this as a validation problem instead of a construction problem.
- error
Forgetting that the right half must be the reverse of the built left half, not another sorted copy in forward order.
进阶变体
外企场景- arrow_right_alt
Return any palindromic rearrangement instead of the lexicographically smallest one, which removes the need to prioritize smaller letters first.
- arrow_right_alt
Use a larger character set where you may need a hash map plus sorting of keys instead of fixed-size counting sort.
- arrow_right_alt
Ask for the largest palindromic rearrangement, which flips the ordering strategy on the left half from ascending to descending.