// 演算法同 C 版：貪心分組 + 三種情況排版 / Same algorithm as C: greedy grouping + 3-case formatting.
// 用 std::string 自動管理記憶體，append(n, ch) 直接重複空格 / std::string handles memory; append(n,ch) repeats a char.

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;          // 最終輸出 / final output lines
        int n = (int)words.size();      // 單字總數 / total word count
        int i = 0;                      // 當前行的第一個單字 / first word index of the current line

        while (i < n) {
            // ---- 階段 1：找出能放入這行的單字範圍 [i, j) / Find the word range that fits ----
            int j = i;                  // j 會停在第一個放不下的單字 / j stops at the first word that won't fit
            int lineLen = 0;            // 字母總長（不含空格）/ letter-only length so far
            while (j < n &&
                   lineLen + (int)words[j].size() + (j - i) <= maxWidth) {
                lineLen += (int)words[j].size();   // 加上這個單字的字母數 / add letter count
                ++j;                               // 試下一個單字 / try next
            }

            int wordCount   = j - i;                // 這行單字數量 / number of words this line
            int totalSpaces = maxWidth - lineLen;   // 剩餘要填入的空格 / spaces left to fill

            // ---- 階段 2：根據情況組裝這行 / Build the line by case ----
            string line;
            line.reserve(maxWidth);                 // 預先保留容量避免重新配置 / reserve to avoid reallocs

            if (j == n || wordCount == 1) {
                // 最後一行或單字行 → 左對齊 / Last line or single-word line → left-justify
                for (int k = i; k < j; ++k) {
                    line += words[k];               // 串接單字 / append the word
                    if (k < j - 1) line += ' ';     // 單空格分隔 / single space between words
                }
                line.append(maxWidth - line.size(), ' '); // 右側補空格 / pad the right side
            } else {
                // 一般行：平均分配 / Regular line: distribute spaces evenly
                int gaps       = wordCount - 1;      // 空隙數 / gap count
                int baseSpaces = totalSpaces / gaps; // 每隙基本空格 / base per gap
                int extra      = totalSpaces % gaps; // 左側多分的空格數 / extras going to left gaps

                for (int k = i; k < j; ++k) {
                    line += words[k];                // 接上單字 / append word
                    if (k < j - 1) {                 // 不是最後一個單字 / not the last word on this line
                        int spaces = baseSpaces + ((k - i) < extra ? 1 : 0); // 前 extra 個 gap +1 / first `extra` gaps get +1
                        line.append(spaces, ' ');    // 一次塞 spaces 個空格 / push that many spaces at once
                    }
                }
            }
            result.push_back(std::move(line));       // move 進結果，省一次複製 / move into result to avoid copy
            i = j;                                   // 下一行從 j 開始 / next line begins at j
        }
        return result;                               // 回傳全部行 / return all lines
    }
};