// 演算法：三次反轉 + 原地壓縮空白。
// Algorithm: three reversals + in-place space compaction.
// (1) 反轉整個字串 / reverse the whole buffer.
// (2) 反轉每個單字 / reverse each word individually.
// (3) 用寫入指標重新排版，去除多餘空白 / use a write pointer to remove extra spaces.

#include <string.h>   // strlen — 取得字串長度 / get string length

// 反轉 s[l..r]（含兩端）的字元 / Reverse characters of s[l..r] inclusive.
static void reverseRange(char *s, int l, int r) {
    while (l < r) {                      // 當左指針還在右指針左邊 / while left is still left of right
        char t = s[l];                   // 暫存左邊字元 / stash the left character
        s[l] = s[r];                     // 把右邊搬到左邊 / move right char into left slot
        s[r] = t;                        // 再把暫存的放到右邊 / place the stashed char into right slot
        l++;                             // 左指針往右走一格 / advance left
        r--;                             // 右指針往左走一格 / retreat right
    }
}

// LeetCode 要求的函式簽名 / LeetCode-required signature.
// 回傳的字串可以是原 buffer（原地修改）/ returned string may be the same buffer (in-place).
char* reverseWords(char* s) {
    int n = (int)strlen(s);              // n = 字串長度 / length of s

    // Step 1：反轉整個字串 / reverse the entire buffer.
    reverseRange(s, 0, n - 1);           // 把 s[0..n-1] 整段反轉 / flip the whole range

    // Step 2：逐一反轉每個單字 / reverse every word in place.
    int i = 0;                           // 掃描指標 / scanning index
    while (i < n) {
        while (i < n && s[i] == ' ') i++; // 跳過空白 / skip spaces between words
        int j = i;                       // j 指向單字開頭 / j marks the word's start
        while (j < n && s[j] != ' ') j++; // 把 j 推到單字結尾後一格 / push j just past the word
        if (i < j) {                     // 若真的找到了一個單字 / if a word was found
            reverseRange(s, i, j - 1);   // 反轉 s[i..j-1]（單字本身）/ reverse this word
        }
        i = j;                           // 從單字之後繼續掃描 / continue after the word
    }

    // Step 3：壓縮多餘空白，重寫回 s / compact spaces by rewriting s in place.
    int w = 0;                           // w = 下一個寫入位置 / next write slot
    int r = 0;                           // r = 讀取位置 / read position
    int wroteWord = 0;                   // 是否已經寫過至少一個單字 / have we written any word yet
    while (r < n) {
        if (s[r] != ' ') {               // 讀到非空白：屬於某個單字 / non-space: part of a word
            if (wroteWord) {             // 不是第一個單字 → 先補一個空白 / not first word → add separator
                s[w++] = ' ';            // 寫入分隔空白 / write the single space
            }
            while (r < n && s[r] != ' ') { // 把整個單字搬過去 / copy the whole word
                s[w++] = s[r++];         // 一個字元一個字元複製 / character by character
            }
            wroteWord = 1;               // 標記已寫過單字 / mark that we've emitted a word
        } else {
            r++;                         // 是空白：直接略過 / it's a space: skip it
        }
    }
    s[w] = '\0';                         // C 字串結尾符號 / NUL-terminate the C string

    return s;                            // 回傳同一塊 buffer / return the same buffer (in-place)
}