3517. Smallest Palindromic Rearrangement I

題目 / Problem

中文： 給你一個回文字串 s（正著讀和倒著讀完全一樣，例如 "aba"、"abba"）。你需要把它的字母重新排列，得到一個同樣是回文、而且字典序最小的字串，並回傳它。所謂「字典序最小」，就是像字典排序那樣，越靠前的位置字母越小越好（a < b < c < ...）。

English: You are given a palindromic string s (it reads the same forwards and backwards, e.g. "aba", "abba"). Rearrange its letters to form another palindrome that is lexicographically smallest, and return it. "Lexicographically smallest" means: compare like dictionary order — make the earliest positions hold the smallest possible letters (a < b < c < ...).

Constraints / 限制： - 1 <= s.length <= 10^5 - s 只由小寫英文字母組成 / s consists of lowercase English letters. - s 保證是回文 / s is guaranteed to be palindromic.

Worked example / 範例： s = "babab" → output "abbba". The letters {a, a, b, b, b} rearranged into the smallest palindrome give "abbba".

名詞解釋 / Glossary

• 回文 / Palindrome: 正著讀和倒著讀一樣的字串。/ A string that reads identically forwards and backwards, e.g. "abcba".
• 字典序 / Lexicographic order: 像字典排列單字的順序：先比第一個字母，相同再比第二個，依此類推；字母越小排越前。/ Dictionary-style ordering: compare position by position; a smaller letter earlier makes the whole string smaller.
• 頻率陣列 / Frequency (count) array: 一個大小為 26 的整數陣列，freq[c] 記錄字母 c 出現幾次。因為只有 26 個小寫字母，用固定陣列比雜湊表更快更省。/ A size-26 integer array where freq[c] stores how many times letter c appears — perfect for 26 lowercase letters.
• 雙指針 / Two pointers: 用兩個索引（一個從左往右 left，一個從右往左 right）同時往中間移動，一次處理回文的兩個對稱位置。/ Two indices moving toward the center, filling the two mirror positions of the palindrome at once.
• 中間字元 / Middle character: 當字串長度為奇數時，正中央那一格。回文中只有它（也只能有它）可以有奇數個。/ For odd-length strings, the exact center slot — the only character allowed to have an odd count.
• malloc / 動態配置記憶體: C 語言中向系統要一塊記憶體來存結果字串；LeetCode 要求回傳的字串必須用 malloc 配置。/ Allocates memory at runtime for the result string, as LeetCode's C harness expects.

思路

中文： 先想暴力法：把所有排列都列出來，篩掉不是回文的，再取字典序最小的。但長度可達 $10^5$，排列數是天文數字，完全不可行。所以我們要直接「構造」答案。關鍵觀察：回文由兩個互為鏡像的半邊組成——左半邊決定後，右半邊就是它的反轉，中間可能有一個單獨字元。因為右半邊完全由左半邊鏡射而來，要讓整個字串字典序最小，只要讓左半邊字典序最小即可。那左半邊怎麼最小？把每個字母的數量除以二（回文中每個字母成對出現，一半放左、一半放右），然後從 a 到 z 由小到大依序填入左半邊，自然就是最小的。長度為奇數時，會恰好有一個字母出現奇數次，把它放到正中間（它放哪都不影響左半邊排序，放中間最不影響字典序）。實作上用雙指針：left 從頭、right 從尾，依字母順序同時填兩端，保證鏡像對稱；最後若有奇數字元填入中央。這樣一次掃描就完成，$O(n)$。

English: Brute force — enumerate all permutations, keep the palindromic ones, pick the smallest — is hopeless: with length up to $10^5$ the number of permutations is astronomical. Instead we construct the answer directly. The key insight (from the hints): a palindrome is two mirror-image halves plus an optional single middle character. Since the right half is forced to be the reverse of the left half, minimizing the whole string reduces to minimizing the left half. To make the left half smallest, we halve each letter's count (letters come in pairs in a palindrome — one of each pair goes left, its mirror goes right) and lay them out from a up to z. If the length is odd, exactly one letter has an odd count; that leftover goes in the exact center, where it can't hurt the left-half ordering. We implement this with two pointers: left fills from the front and right from the back, placing the same letter at both ends in alphabetical order to keep the mirror symmetry. One pass, $O(n)$.

逐步走查 / Walkthrough

Example input s = "babab" (length n = 5).

Step 0 — Count / 計數頻率：

We allocate res of size 5, set pointers left = 0, right = 4, and mid = -1.

Step 1 — process letter a (freq 2, even) / 處理 a： - half = 2/2 = 1. Place one a at both ends. - res[0]='a', res[4]='a' → res = "a...a" - left = 1, right = 3.

Step 2 — process letter b (freq 3, odd) / 處理 b： - Count is odd → remember mid = 'b' (this letter goes in the center). - half = 3/2 = 1. Place one b at both ends. - res[1]='b', res[3]='b' → res = "ab.ba" - left = 2, right = 2.

Step 3 — fill the middle / 填中間： - mid != -1, so res[left] = res[2] = 'b'. - res = "abbba" ✅

Final answer: "abbba", matching the expected output.

Solution — C

// 演算法：統計每個字母出現次數，取一半由小到大填入兩端(雙指針鏡射)，
//        奇數次的字母放正中央，即得字典序最小的回文。
// Algorithm: count letters; place half of each (a→z) at both ends via two
//            pointers (mirror), put the odd-count letter in the center.

char* smallestPalindrome(char* s) {
    int n = strlen(s);                 // n 是字串長度 / n = length of the string
    int freq[26] = {0};                // 26 個字母的計數，全部初始化為 0 / count of each letter, all zero

    // 掃一遍統計每個字母出現幾次 / one pass to count each letter
    for (int i = 0; i < n; i++)
        freq[s[i] - 'a']++;            // s[i]-'a' 把 'a'..'z' 映成 0..25 當索引 / map letter to index 0..25

    // 向系統要 n+1 個位元組：n 個字元 + 1 個結尾 '' / allocate n chars plus the null terminator
    char* res = malloc(n + 1);
    res[n] = '';                     // C 字串以 '' 結尾，缺了會讀過頭 / C strings end with ''

    int left = 0, right = n - 1;       // 雙指針：left 從頭填、right 從尾填 / two pointers filling both ends
    int mid = -1;                      // 記錄奇數次的字母(要放中間)，-1 表示還沒有 / letter for the center, -1 = none yet

    // 依字母由小到大(a→z)處理，保證前面的位置放最小的字母 / go a→z so earliest slots get smallest letters
    for (int c = 0; c < 26; c++) {
        if (freq[c] % 2 == 1)          // 出現奇數次 → 這個字母該放正中央 / odd count → this one goes in the middle
            mid = c;
        int half = freq[c] / 2;        // 一半放左、一半(鏡射)放右 / half go left, the mirror half go right
        for (int k = 0; k < half; k++) {
            res[left++] = 'a' + c;     // 左端放字母，指針右移 / place at left end, advance left
            res[right--] = 'a' + c;    // 右端放同一字母(鏡射)，指針左移 / mirror at right end, retreat right
        }
    }

    // 若長度為奇數，此時 left == right 指向正中央，填入那個奇數字元 / odd length: fill the exact center
    if (mid != -1)
        res[left] = 'a' + mid;

    return res;                        // 回傳配置好的結果，LeetCode 會負責釋放 / return the allocated string
}

Solution — C++

// 演算法：用計數陣列統計字母，取一半由小到大填入兩端(雙指針鏡射)，
//        奇數次的字母放正中央，得到字典序最小的回文。
// Algorithm: count letters, mirror-fill both ends a→z with two pointers,
//            place the odd-count letter in the center.
class Solution {
public:
    string smallestPalindrome(string s) {
        int n = s.size();                     // 字串長度 / length of the string
        vector<int> freq(26, 0);              // vector 是動態陣列，這裡當 26 字母計數，初值 0 / dynamic array as letter counts

        // range-for：直接取出每個字元 ch / range-for loops over each character directly
        for (char ch : s)
            freq[ch - 'a']++;                 // ch-'a' 得到 0..25 索引 / convert letter to index 0..25

        string res(n, ' ');                   // 建立長度 n、先填空格的字串，稍後覆寫 / string of n slots to overwrite
        int left = 0, right = n - 1;          // 雙指針，一頭一尾 / two pointers at the two ends
        int mid = -1;                         // 中間字元(奇數次的那個)，-1 代表沒有 / center letter, -1 if none

        // 依 a→z 順序，讓最小字母填在最前面 / iterate a→z so smallest letters land first
        for (int c = 0; c < 26; c++) {
            if (freq[c] % 2 == 1)             // 奇數次 → 放中間 / odd count → belongs in the center
                mid = c;
            int half = freq[c] / 2;           // 成對出現，一半在左一半鏡射到右 / pairs split left/right
            for (int k = 0; k < half; k++) {
                res[left++]  = 'a' + c;       // 左端寫入並右移 / write at left, advance
                res[right--] = 'a' + c;       // 右端鏡射寫入並左移 / mirror at right, retreat
            }
        }

        if (mid != -1)                        // 奇數長度時 left==right 為正中央 / odd length: center slot
            res[left] = 'a' + mid;

        return res;                           // 回傳結果字串 / return the result
    }
};

複雜度 / Complexity

• Time: O(n) — 統計字母掃一遍是 $O(n)$；填入結果時，所有字母的 half 加起來最多也是 $n/2$ 對，外層 26 個字母是常數。所以由字串長度 $n$ 主導。/ Counting is one pass over $n$. Filling touches each of the $n$ positions once (the total of all half values is $\le n/2$ pairs); the 26-letter outer loop is a constant. Dominated by $n$.
• Space: O(n) — 需要一塊大小 $n$ 的結果字串。頻率陣列只有 26 格，是常數 $O(1)$，不影響級別。/ We allocate the result string of size $n$. The frequency array is a fixed 26 slots ($O(1)$), so the result string dominates.

Pitfalls & Edge Cases

• 忘記 malloc 結果字串 (C) / Forgetting to malloc in C: 在 C 裡回傳區域陣列的指標會在函式結束後失效，必須用 malloc；別忘了配置 n+1 並寫入 '\0'，否則字串沒有結尾會亂印。/ Returning a stack array is undefined behavior; allocate n+1 bytes and write the terminating '\0'.
• 中間字元的處理 / The middle character: 只有奇數長度才有中央格。程式用 mid == -1 判斷是否需要填中間，偶數長度時 left 會停在 right+1，不會誤寫。/ Only odd lengths have a center; the mid == -1 guard skips it for even lengths (where left ends past right).
• 必須按 a→z 順序 / Must iterate in alphabetical order: 若不按字母由小到大填，就無法保證字典序最小。外層迴圈的順序正是這個保證的來源。/ Filling out of order breaks the "smallest" guarantee; the c = 0..25 loop is exactly what enforces it.
• 依賴輸入是回文 / Relies on the input being a palindrome: 題目保證每個字母除了最多一個外都成對出現，所以 mid 最多被設定一次。若輸入不是回文，這個假設會失效——但題目已保證。/ The guarantee means at most one odd-count letter, so mid is set at most once. The algorithm leans on this promise.
• 單一字元 / Single character (e.g. "z"): freq['z']=1 為奇數，mid='z'，half=0，直接填中間得 "z"。邊界正確。/ Handled correctly: half=0, mid fills the lone slot.