日期：2026年7月28日
LeetCode 題目連結：3517. Smallest Palindromic Rearrangement I
解題想法
中等難度題，題目給一個迴文字串 $s$，要將 $s$ 重新排列成字典序最小的迴文字串。我一開始想到的寫法，是先計算各個字母的數量，如果字串 $s$ 長度 $n$ 為奇數，則所有的字母之中只有一個字母的數量是奇數。接下來依照字典序及數量産生需要使用的字母，開一個長度為 $n$ 的串列 $arr$ 儲存答案，由串列兩端向中央依序填入字母。如果 $n$ 是奇數，則 $arr$ 中央再填入唯一的奇數數量字母。最後將 $arr$ 組成字串後回傳。不過這樣寫實在太慢。
後來想到題目給的字串 $s$ 本身就是迴文字串，只要取 $s$ 的左半邊子字串 $left$ 再排序，答案的右半邊 $right$ 就是 $left$ 反序。如果 $s$ 的長度 $n$ 是奇數，$left$ 及 $right$ 之中再加上 $s[n/2]$ 即可。這個寫法的速度快很多。
Python 程式碼
Runtime: 375 ms, beats 21.66%. Memory: 22.32 MB, beats 5.07%.
class Solution:
def smallestPalindrome(self, s: str) -> str:
n = len(s)
cnt = Counter(s)
chars = []
odd = "" # 奇數數量字母
# 依照字母順序取出數量為偶數的字母
for ch, val in sorted(cnt.items()):
if val % 2 == 1:
chars += [ch] * (val - 1)
odd = ch
else:
chars += [ch] * val
# 由兩側向中央填入字母
arr = [""] * n
for i in range(n//2):
arr[i] = arr[n-i-1] = chars[i*2]
# 奇數長度，中間放唯一一個奇數數量的字母
if n%2 == 1:
arr[n//2] = odd
# 組成字串再回傳
return "".join(arr)
Runtime: 247 ms, beats 59.91%. Memory: 20.66 MB, beats 91.71%.
class Solution:
def smallestPalindrome(self, s: str) -> str:
n = len(s)
left = "".join(sorted(s[:n//2])) # 取左半邊字母並排序
if n%2 == 1: # 奇數長度
return left + s[n//2] + left[::-1] # 右半邊字母為左半邊字母反序，加上中間的字母
else:
return left + left[::-1] # 右半邊字母為左半邊字母反序
