3302. Find the Lexicographically Smallest Valid Sequence

題目 / Problem

中文： 給你兩個字串 word1 和 word2。

• 如果最多修改 x 中的一個字元就能讓它變得跟 y 完全一樣，就說 x 「幾乎等於」y（almost equal）。
• 一個索引序列 seq 是「有效的」（valid），需要滿足：索引是嚴格遞增的，而且把 word1 在這些索引上的字元依序拼起來，得到的字串「幾乎等於」word2。

請回傳一個長度為 word2.length 的陣列，代表字典序最小的有效索引序列；若不存在，回傳空陣列。注意：要比較的是索引陣列本身的字典序，不是拼出來的字串。

English: You are given two strings word1 and word2.

• x is almost equal to y if changing at most one character in x makes it identical to y.
• An index sequence seq is valid if the indices are strictly increasing and the characters of word1 picked at those indices (in order) form a string that is almost equal to word2.

Return the lexicographically smallest valid sequence of indices (length word2.length), or an empty array if none exists. The lexicographic comparison is on the array of indices, not on the resulting string.

Constraints / 限制： - 1 <= word2.length < word1.length <= 3 * 10^5 - Both strings contain only lowercase English letters.

Worked example (Example 2): word1 = "bacdc", word2 = "abc" → [1,2,4]. - word1[1]='a' matches 'a'. - word1[2]='c' is changed to 'b' (this is our one allowed change). - word1[4]='c' matches 'c'.

名詞解釋 / Glossary

• 子序列 / Subsequence：從一個字串中「按原順序」挑出若干字元（可跳過中間的），組成的新字串。例如 "ace" 是 "abcde" 的子序列。挑選的字元索引必須遞增。
• 後綴 / Suffix：字串從某個位置一直到結尾的那一段。word2 的一個後綴例如 "bc"（"abc" 去掉開頭的 a）。
• 動態規劃 / Dynamic Programming (DP)：把大問題拆成小問題，把小問題的答案存進陣列，避免重複計算。這裡用 dp[i] 記錄「從 word1 的第 i 位開始，最多能對上 word2 多長的後綴」。
• 貪心 / Greedy：每一步都選當下看起來最好的選項（這裡是「最小的可用索引」），並證明這樣能得到全域最佳解。
• 雙指針 / Two pointers：用兩個索引 i（掃 word1）與 j（掃 word2）同時往前走，比對字元。
• 字典序最小 / Lexicographically smallest：比較兩個陣列時，從第一個元素開始逐位比，第一個不同的位置較小者，整個陣列就較小。所以「越前面的索引越小越好」，優先權高於後面的索引。
• 幾乎相等 / Almost equal：最多允許一個字元不一樣（即最多用一次「修改額度」）。

思路

中文： 最直觀的暴力法是：嘗試所有可能的索引序列，看哪個「幾乎等於」word2 又字典序最小。但索引組合數是指數級的，word1 長度可達 3×10⁵，完全跑不動。

關鍵觀察是「幾乎相等」= 最多一次修改。所以有效序列裡最多只有一個位置是「不匹配但被修改成對的」，其餘位置都必須是精確匹配。我們想要字典序最小，就要讓越前面的索引越小，因此策略是：從左往右一個一個決定 word2[j] 該放哪個 word1 的索引，每次都取「還能讓後面全部完成」的最小索引。

難點在於：當 word1[i] 和 word2[j] 不一樣時，我要不要「花掉」那唯一的修改額度在這裡？花掉當然能拿到更小的索引 i（對字典序有利），但前提是剩下的字元還能全部精確匹配。為了快速判斷這件事，我們預先算一個 dp 陣列：dp[i] = 從 word1[i..] 出發，最多能精確對上 word2 多長的後綴。它可以從右往左 O(n) 算出：若 word1[i] 正好等於「還沒對上的那個後綴字元」word2[m-1-dp[i+1]]，就 dp[i]=dp[i+1]+1，否則 dp[i]=dp[i+1]。

有了 dp，貪心就很清楚了。用指針 i 掃 word1、j 指向 word2 目前要放的字元，並記一個布林值 changed 表示修改額度是否已用掉： 1. 若 word1[i] == word2[j]：直接精確匹配，記下 i，i 和 j 都前進。（精確匹配不花額度，且索引最小，永遠最優。） 2. 否則若還沒改過，且 dp[i+1] >= (剩下要放的字元數 m-1-j)：代表在此處用掉修改額度後，後面還能全部精確對上，於是就在此用掉額度，記下 i。 3. 否則跳過這個索引（i++）。 若最後 j 走到底（m 個都放好了）就回傳答案，否則回傳空陣列。

為什麼「能匹配就馬上匹配、能改就馬上改」是對的？因為索引 i 是當下最小的可選位置，把更小的索引放到更前面的位置，字典序一定更小，且只要當前狀態本來就有解，這樣選不會破壞後面的可行性（精確匹配不耗額度、用額度前我們已用 dp 確認過可行）。

English: Brute force — trying every index subsequence — is exponential and hopeless for word1 up to 3×10⁵. The key insight is that "almost equal" means at most one change, so in any valid sequence at most one picked position is a mismatch we "fix", and every other position must be an exact match.

Because we want the lexicographically smallest array of indices, earlier positions dominate, so we decide word2[j]'s index left to right and always grab the smallest index that still lets us finish. The tricky decision: when word1[i] != word2[j], should we spend our single change here? Spending it gives a smaller index (good for lex order), but only if everything after can still match exactly. To test that instantly we precompute dp[i] = the longest suffix of word2 matchable as an exact subsequence of word1[i..], filled right-to-left in O(n): if word1[i] equals the next unmatched suffix char word2[m-1-dp[i+1]], then dp[i]=dp[i+1]+1, else dp[i]=dp[i+1].

Now the greedy uses two pointers i (over word1), j (over word2) and a flag changed: 1. If word1[i]==word2[j], take an exact match (no budget used, smallest index — always optimal), advance both. 2. Else if we haven't changed yet and dp[i+1] >= m-1-j (the remaining m-1-j chars can still all match exactly), spend the change here and take index i. 3. Else skip this index (i++).

If j reaches m, return the collected indices; otherwise return an empty array. Taking the earliest match/change is safe because a smaller index in an earlier slot always wins lexicographically, an exact match spends no budget, and we only spend the change after dp confirms the rest stays feasible.

逐步走查 / Walkthrough

Example: word1 = "bacdc", word2 = "abc" (n=5, m=3). Answer should be [1,2,4].

Step 1 — build dp (right to left). dp[i] = longest suffix of "abc" matchable exactly from word1[i..]. We compare word1[i] against word2[m-1-dp[i+1]] (the next suffix char still needed).

So dp = [2, 1, 1, 1, 1, 0].

Step 2 — greedy scan with i=0, j=0, changed=false, res=[]:

j reached m=3 → return [1,2,4]. ✅

Notice at i=0 we did not grab the small index 0 with a change, because dp proved the rest ("bc") could not then be matched — spending the change there would strand us.

Solution — C

// 演算法 / 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;
}

Solution — C++

// 演算法同 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
    }
};

複雜度 / Complexity

• Time: O(n)，其中 n = word1.length。填 dp 陣列從右往左掃一遍是 O(n)；貪心用雙指針從左往右掃一遍，i 只會前進、絕不回退，所以也是 O(n)。兩趟線性掃描相加仍是 O(n)。/ Building dp is one right-to-left pass; the greedy is one left-to-right pass where i only ever moves forward — two linear passes, O(n) total. (m ≤ n, so it doesn't dominate.)
• Space: O(n)，主要是長度 n+1 的 dp 陣列；答案陣列長度 m 通常不計入額外空間（或算 O(m) ≤ O(n)）。/ Dominated by the dp array of size n+1; the output of size m is ≤ O(n).

Pitfalls & Edge Cases

• dp[i+1] 的邊界 / boundary of dp[i+1]：貪心裡讀取 dp[i+1]，i 最大為 n-1，因此要存取 dp[n]。務必把 dp 開成 n+1 格並設 dp[n]=0，否則會越界。/ We read dp[i+1] with i up to n-1, so dp[n] must exist — allocate n+1 slots.
• 可行性檢查別漏 / don't skip the feasibility check：不匹配時若不驗 dp[i+1] >= m-1-j 就亂用額度，可能把額度浪費在早處，導致後面對不齊卻已無額度。dp 正是用來保證「用掉後剩下仍能精確對上」。/ Spending the change without the dp check can strand you with no budget for a later required mismatch.
• m-1-j 何時為 0 / when m-1-j is 0：j 在最後一格 (m-1) 時 m-1-j=0，任何 dp[i+1] >= 0 都成立——最後一個字元用修改額度永遠可行（後面沒東西要對了）。這是正確行為，不是 bug。/ At the last char the remaining count is 0, so a change is always allowed there — intended, not a bug.
• 優先精確匹配 / prefer exact match first：即使還有額度，只要 word1[i]==word2[j] 就該精確匹配，因為它不花額度又給出最小索引；先檢查匹配、再檢查是否用額度，順序不能反。/ Check exact match before considering a change; matching costs no budget and gives the smallest index.
• 無解要回傳空陣列 / return empty on failure：若掃完仍 j < m，代表湊不齊，必須回傳空陣列（C 版設 *returnSize=0 並釋放暫存；C++ 回傳 {}）。別回傳半成品。/ If j < m after the scan, return an empty array, not a partial one.
• 記憶體釋放 / free memory (C)：C 版 dp 用完要 free；無解時也要 free(res)，避免記憶體洩漏。C++ 的 vector 會自動釋放，不用手動處理。/ In C, free dp (and res on failure); C++ vector cleans up automatically.
• 索引嚴格遞增自然成立 / strictly increasing comes for free：i 只前進，記錄的索引自然嚴格遞增，無需額外檢查。/ Since i only advances, recorded indices are automatically strictly increasing.