// 演算法：統計每個字母出現次數，取一半由小到大填入兩端(雙指針鏡射)，
//        奇數次的字母放正中央，即得字典序最小的回文。
// 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 個結尾 '\0' / allocate n chars plus the null terminator
    char* res = malloc(n + 1);
    res[n] = '\0';                     // C 字串以 '\0' 結尾，缺了會讀過頭 / C strings end with '\0'

    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
}