// 演算法同 C 版 / Same algorithm as the C version:
//   1) dp[i] = word1[i..] 能精確對上的 word2 最長後綴長度（右→左）。
//   2) 左→右貪心：能匹配就匹配；否則若額度未用且 dp 保證後續可行就用掉額度；否則跳過。
//   回傳字典序最小的有效索引序列，或空陣列。

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

class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        int n = word1.size();       // word1 長度 / length of word1
        int m = word2.size();       // word2 長度 / length of word2

        // vector<int> 是會自動管理記憶體的動態陣列；(n+1, 0) 建立 n+1 個 0
        // vector<int> is a self-managing dynamic array; (n+1, 0) makes n+1 zeros
        vector<int> dp(n + 1, 0);   // dp[n]=0 已由初始化保證 / dp[n]=0 given by init

        // 由右往左填 dp / fill dp from right to left
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = dp[i + 1];      // 預設沿用 / default carry-over
            // 若仍有後綴字元待對上，且 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;
        }

        vector<int> res;            // 存放答案索引 / holds the answer indices
        res.reserve(m);             // 預留 m 格避免多次擴容 / reserve m slots to avoid reallocation
        int j = 0;                  // 下一個要放的 word2 字元 / next char of word2 to place
        bool changed = false;       // 修改額度是否已用 / whether the single change is spent

        // 雙指針掃描 / two-pointer scan over word1
        for (int i = 0; i < n && j < m; ) {
            if (word1[i] == word2[j]) {
                // 情況1：精確匹配，最優 / Case 1: exact match, optimal
                res.push_back(i);   // push_back 把元素加到尾端 / append index to the vector
                ++i; ++j;
            } else if (!changed && dp[i + 1] >= m - 1 - j) {
                // 情況2：在此花掉修改額度仍能完成 / Case 2: spending the change here still finishes
                changed = true;
                res.push_back(i);
                ++i; ++j;
            } else {
                // 情況3：跳過此索引 / Case 3: skip this index
                ++i;
            }
        }

        // 若沒放滿 m 個字元代表無解，回傳空 vector（即空陣列）
        // if fewer than m chars were placed, no solution exists → return empty vector
        if (j == m) return res;
        return {};                  // {} 建立一個空 vector / {} makes an empty vector
    }
};