// 演算法：兩階段 / Two-phase algorithm.
// 1) 用雙指標貪心地把單字分組到每一行 / Two-pointer greedy grouping per line.
// 2) 對每一行依「最後一行 / 單字行 / 一般行」三種情況排版 / Format each line by case.
// 時間 O(總字元數), 空間 O(輸出大小) / Time O(total chars), space O(output size).

#include <stdlib.h>   // malloc, free / 動態記憶體
#include <string.h>   // strlen, memcpy / 字串長度與位元組複製

char** fullJustify(char** words, int wordsSize, int maxWidth, int* returnSize) {
    // 最多每個單字一行，所以行數上限 = wordsSize / At most one word per line, so cap = wordsSize.
    char** result = (char**)malloc(sizeof(char*) * wordsSize);
    int lineCount = 0;            // 已產生的行數 / number of lines produced so far
    int i = 0;                    // 這一行的第一個單字 index / first word index of current line

    while (i < wordsSize) {
        // ---- 階段 1：決定這一行放哪些單字 / Pick words that fit on this line ----
        int j = i;                // j 會掃到第一個放不下的單字 / j scans to the first word that won't fit
        int lineLen = 0;          // 只計算字母長度，不含空格 / letter length only, no spaces yet
        // 條件：放完 words[j] 後仍需 (j - i) 個分隔空格 / after taking words[j] we still need (j-i) separators
        while (j < wordsSize &&
               lineLen + (int)strlen(words[j]) + (j - i) <= maxWidth) {
            lineLen += (int)strlen(words[j]);  // 累加字母長度 / accumulate letter count
            j++;                               // 嘗試下一個單字 / try next word
        }
        // 此時 words[i..j-1] 是這行的單字 / words[i..j-1] are the chosen words

        int wordCount   = j - i;                  // 這行有幾個單字 / how many words on this line
        int totalSpaces = maxWidth - lineLen;     // 還需要塞入幾個空格 / total spaces to place

        // ---- 階段 2：把這行字串建出來 / Build the line string ----
        // 配置 maxWidth + 1 個 byte（多 1 個放 '\0'）/ allocate maxWidth + 1 bytes (one for '\0')
        char* line = (char*)malloc(maxWidth + 1);
        int pos = 0;                              // line 目前的寫入位置 / current write index in line

        // 最後一行 OR 只有 1 個單字 → 左對齊 / Last line or single-word line → left-justify
        if (j == wordsSize || wordCount == 1) {
            for (int k = i; k < j; k++) {
                int len = (int)strlen(words[k]);
                memcpy(line + pos, words[k], len);    // 複製單字到 line / copy word bytes
                pos += len;                            // 移動寫入指標 / advance write pointer
                if (k < j - 1) {                       // 不是最後一個單字 / not the last word
                    line[pos++] = ' ';                 // 單空格分隔 / single space separator
                }
            }
            while (pos < maxWidth) line[pos++] = ' '; // 行尾補空格 / pad trailing spaces
        } else {
            // 一般行：平均分配空格 / Regular line: distribute spaces evenly
            int gaps       = wordCount - 1;            // 空隙數 / number of gaps
            int baseSpaces = totalSpaces / gaps;       // 每隙的基本空格 / base spaces per gap
            int extra      = totalSpaces % gaps;       // 餘下的空格從左邊先發 / leftover spaces, leftmost first

            for (int k = i; k < j; k++) {
                int len = (int)strlen(words[k]);
                memcpy(line + pos, words[k], len);     // 寫入單字 / write the word
                pos += len;
                if (k < j - 1) {                       // 不是最後一個就要放空格 / not last → add gap
                    // 前 extra 個空隙多放 1 個空格 / first `extra` gaps get one extra space
                    int spaces = baseSpaces + ((k - i) < extra ? 1 : 0);
                    for (int s = 0; s < spaces; s++) line[pos++] = ' ';
                }
            }
        }
        line[maxWidth] = '\0';        // C 字串結尾 / null-terminate the C string
        result[lineCount++] = line;   // 收進結果陣列 / store the line in the result array
        i = j;                        // 下一行從 j 開始 / next line begins at j
    }

    *returnSize = lineCount;          // 透過輸出參數回傳行數 / report total lines back via out-param
    return result;                    // 回傳指向所有行的指標陣列 / return the array of line pointers
}