LeetCode 解題筆記：3517. Smallest Palindromic Rearrangement I

作者：王一哲
日期：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]  # 右半邊字母為左半邊字母反序

C++ 程式碼

Runtime: 176 ms, beats 9.89%. Memory: 85.24 MB, beats 5.05%.

class Solution {
public:
    string smallestPalindrome(string s) {
        int n = (int)s.size();  // 長度
        map<char, int> cnt;  // 計數器
        for(char c : s) cnt[c]++;
        // 依照字母順序取出數量為偶數的字母
        string chars;
        char odd;
        for(auto it : cnt) {
            string t (it.second - (it.second % 2 == 1), it.first);
            chars += t;
            if (it.second % 2 == 1) odd = it.first;
        }
        // 由兩側向中央填入字母
        string ans (n, '@');
        for(int i = 0; i < n/2; i++) {
            ans[i] = chars[i*2];
            ans[n-i-1] = chars[i*2];
        }
        // 奇數長度，加上中間的字母
        if (n%2 == 1) ans[n/2] = odd;
        return ans;
    }
};

Runtime: 68 ms, beats 43.52%. Memory: 69.54 MB, beats 66.59%.

class Solution {
public:
    string smallestPalindrome(string s) {
        int n = (int)s.size();
        string left = s.substr(0, n/2);  // 取左半邊字母並排序
        sort(left.begin(), left.end());
        string right (left.crbegin(), left.crend());  // 右半邊字母為左半邊字母反序
        if (n%2 == 1) {  // 奇數長度
            return left + s[n/2] + right;  // 加上中間的字母
        } else {
            return left + right;
        }
    }
};