// 演算法：用計數陣列統計字母，取一半由小到大填入兩端(雙指針鏡射)，
//        奇數次的字母放正中央，得到字典序最小的回文。
// 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
    }
};