// 演算法 / Algorithm:
// 對每個字串算一個長度 26 的字母計數，編碼成「簽名」字串；
// 簽名相同 = 同組易位構詞。用簽名陣列分組（這裡用線性比對找已存在的簽名）。
// For each string, build a 26-letter count, encode it into a signature string;
// equal signatures = same anagram group. Group by matching signatures.

#include <stdlib.h>   // malloc / free / qsort
#include <string.h>   // strcmp / strlen / strcpy

// 比較函式給 qsort 用：把字串裡的字元由小到大排序
// Comparator for qsort: sorts characters ascending.
static int cmp_char(const void *a, const void *b) {
    // *(char*)a 把 void* 轉回 char* 再取值 / cast void* back to char* and dereference
    return (*(const char *)a) - (*(const char *)b);
}

// 回傳值：char***（指向「字串陣列的陣列」），即每組是一個 char**
// Returns char*** : an array of groups, each group being a char** (array of strings).
char ***groupAnagrams(char **strs, int strsSize,
                      int *returnSize, int **returnColumnSizes) {
    // keys[i] 存第 i 組的簽名；用來判斷新字串該歸到哪一組
    // keys[i] holds group i's signature, used to decide which group a string joins.
    char **keys   = (char **)malloc(sizeof(char *) * strsSize);   // 最多 strsSize 組 / at most strsSize groups
    char ***groups = (char ***)malloc(sizeof(char **) * strsSize); // 每組的字串清單 / list per group
    int *counts   = (int *)malloc(sizeof(int) * strsSize);         // 每組目前有幾個字串 / size of each group
    int groupCnt  = 0;                                             // 目前共幾組 / number of groups so far

    for (int i = 0; i < strsSize; i++) {
        // ---- 步驟 A：替 strs[i] 算簽名（排序它的字元複本）----
        // Step A: compute signature of strs[i] by sorting a copy of its chars.
        int len = (int)strlen(strs[i]);                 // 字串長度（不含結尾 '\0'）/ length excluding NUL
        char *sig = (char *)malloc(len + 1);            // +1 給字串結尾 '\0' / +1 for the terminator
        strcpy(sig, strs[i]);                           // 複製一份，避免改到原字串 / copy so we don't mutate input
        qsort(sig, len, sizeof(char), cmp_char);        // 原地排序字元 / sort chars in place -> signature

        // ---- 步驟 B：在已有的組裡找相同簽名 ----
        // Step B: search existing groups for a matching signature.
        int g = -1;                                     // -1 表示還沒找到 / -1 means not found yet
        for (int j = 0; j < groupCnt; j++) {
            if (strcmp(keys[j], sig) == 0) {            // strcmp==0 代表兩簽名相等 / equal signatures
                g = j;                                  // 找到所屬組別 / found the group index
                break;
            }
        }

        if (g == -1) {                                  // 沒有相同簽名 → 開新組 / no match -> new group
            g = groupCnt++;                             // 取一個新組編號 / allocate a new group id
            keys[g]   = sig;                            // 這組的簽名就是 sig（沿用，不再 free）/ keep sig as the key
            groups[g] = (char **)malloc(sizeof(char *) * strsSize); // 預留空間 / reserve room
            counts[g] = 0;                              // 新組目前 0 個元素 / starts empty
        } else {
            free(sig);                                  // 已有此組，sig 用不到了，釋放避免漏記憶體 / free unused copy
        }

        // ---- 步驟 C：把原始字串放進該組 ----
        // Step C: append the ORIGINAL string into its group.
        groups[g][counts[g]] = strs[i];                 // 存原字串指標 / store pointer to original string
        counts[g]++;                                    // 該組元素數 +1 / group size +1
    }

    // ---- 步驟 D：依 LeetCode 介面填寫回傳資訊 ----
    // Step D: fill the output parameters required by LeetCode.
    *returnSize = groupCnt;                             // 共幾組 / number of groups
    *returnColumnSizes = (int *)malloc(sizeof(int) * groupCnt); // 每組大小的陣列 / sizes array
    for (int j = 0; j < groupCnt; j++) {
        (*returnColumnSizes)[j] = counts[j];            // 第 j 組有幾個字串 / size of group j
        free(keys[j]);                                  // 簽名已用完，釋放 / signature no longer needed
    }

    free(keys);     // 釋放輔助陣列 / free helper arrays
    free(counts);
    return groups;  // groups 與其子陣列交給 LeetCode 管理 / hand groups to the harness
}