// 演算法 / Algorithm:
//   1) dp[i] = 從 word1[i..] 能精確對上的 word2 最長後綴長度（由右往左算）。
//      dp[i] = longest suffix of word2 matchable as a subsequence of word1[i..].
//   2) 由左往右貪心：能精確匹配就匹配；否則若還沒用過修改額度且 dp 保證
//      剩下能精確對上，就在此用掉額度；否則跳過。取最小可行索引即得字典序最小解。

#include <stdlib.h>   // malloc / free
#include <string.h>   // strlen
#include <stdbool.h>  // bool / true / false

int* validSequence(char* word1, char* word2, int* returnSize) {
    int n = strlen(word1);          // word1 長度 / length of word1
    int m = strlen(word2);          // word2 長度 / length of word2

    // dp 需要 n+1 格，dp[n] 當作「空後綴」的基底 0
    // dp needs n+1 slots; dp[n]=0 is the empty-suffix base case
    int* dp = (int*)malloc((n + 1) * sizeof(int));
    dp[n] = 0;                      // 從 word1 末端之後開始，什麼都對不上 / nothing matched past the end

    // 由右往左填 dp / fill dp from right to left
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = dp[i + 1];          // 預設不新增匹配 / default: carry over previous count
        // 若還有後綴字元待對上，且 word1[i] 正好是那個字元，就延長 1
        // if a suffix char is still needed and word1[i] equals it, extend by 1
        if (dp[i + 1] < m && word1[i] == word2[m - 1 - dp[i + 1]]) {
            dp[i] = dp[i + 1] + 1;
        }
    }

    // 答案最多 m 個索引 / the answer holds at most m indices
    int* res = (int*)malloc(m * sizeof(int));
    int j = 0;                      // 目前要放的 word2 字元 / next char of word2 to place
    bool changed = false;           // 修改額度是否已用掉 / whether the one change is spent

    // 雙指針掃描 word1；i 是 word1 索引 / two-pointer scan over word1
    for (int i = 0; i < n && j < m; ) {
        if (word1[i] == word2[j]) {
            // 情況1：精確匹配，不花額度，索引最小 → 直接採用
            // Case 1: exact match — no budget used, smallest index — take it
            res[j++] = i;           // 記錄索引並讓 j 前進 / record index, advance j
            i++;                    // word1 也前進 / advance i
        } else if (!changed && dp[i + 1] >= m - 1 - j) {
            // 情況2：不匹配，但還沒改過，且剩下 (m-1-j) 個字元能精確對上
            //        → 在此用掉修改額度，換得較小的索引 i
            // Case 2: mismatch, budget free, and the remaining (m-1-j) chars can
            //         still all match exactly → spend the change here for a smaller index
            changed = true;         // 額度用掉 / budget now used
            res[j++] = i;           // 這個索引仍計入答案 / this index still counts
            i++;
        } else {
            // 情況3：既不能匹配也不能改 → 跳過此索引 / skip this index
            i++;
        }
    }

    free(dp);                       // dp 用完釋放記憶體 / free the dp array

    if (j == m) {                   // 全部 m 個字元都放好了 / all m chars placed
        *returnSize = m;
        return res;
    }
    // 找不到有效序列 → 回傳空陣列 / no valid sequence → return empty
    *returnSize = 0;
    free(res);
    return NULL;
}