Greedy with Preprocessing.
Intuition\nGreedy.\nPreprocess word2 pattern to check viable positions for the only mismatched character.\n\n# Approach\nSee details in the solution comments.\n
# Intuition\nGreedy.\nPreprocess word2 pattern to check viable positions for the only mismatched character.\n\n# Approach\nSee details in the solution comments.\n\n# Complexity\n- Time complexity:\nO(n + m)\n\n- Space complexity:\nO(n + m)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string txt, string pttr) {\n        //\n        // Stage A:\n        //\n        // Assume we want to allocate exact suffix pttr[i:] in txt =>\n        // pttr_rmost_suff_beg_in_txt[i] will be rightmost position of pttr[i]\n        // -1 in pttr_rmost_suff_beg_in_txt[i] means can not allocate this exact suffix\n        //\n        vector<int> pttr_rmost_suff_beg_in_txt(pttr.length(), -1);\n        int j = txt.length() - 1;\n        for (int i = pttr.length() - 1; i >= 0 && j >= 0; --i) {\n            while (j > 0 && txt[j] != pttr[i])\n                --j;\n            if (txt[j] != pttr[i]) break;\n            pttr_rmost_suff_beg_in_txt[i] = j;\n            --j;\n        }\n\n        //\n        // Stage B:\n        //\n        // Check every pttr[i] as a potential position for mismatch in \'almost\' equal.\n        // j - will be leftmost possible position in txt to mismatch pttr[i].\n        // pttr_rmost_suff_beg_in_txt helps to detect if the hypothesis of mismatch pttr[i] is viable.\n        // First viable pttr[i] will give lexicographically first answer.\n        //\n        vector<int> res;\n\n        j = 0;\n        for (int i = 0; i < pttr.size(); ++i) {\n            if (pttr[i] == txt[j]) {\n                // Greedy: if match => simply move forward.\n                res.push_back(j++);\n                continue;\n            }\n            int suff_beg = i + 1; // first position of exact match suffix\n            if (suff_beg >= pttr.size() // suffix is empty => viable\n                    || pttr_rmost_suff_beg_in_txt[suff_beg] > j // viable guaranteed by pttr_rmost_suff_beg_in_txt\n                    ) {\n                // Yahoo! Bingo! : viable solution, push suffix allocation and return.\n                res.push_back(j++);\n                for (int k = suff_beg; k < pttr.size(); ++k) {\n                    while (j < txt.size() && txt[j] != pttr[k])\n                        ++j;\n                    // result: {-1} quazi-assert pttr_rmost_suff_beg_in_txt guarantees j will be found.\n                    if (txt[j] != pttr[k]) return {-1};\n                    res.push_back(j++);\n                }\n                return res;\n            }\n            // pttr[i] not viable as mismatch => find match for i-th and try later i.\n            while (j < txt.length() && txt[j] != pttr[i])\n                ++j;\n            if (txt[j] != pttr[i]) return {}; // failed to find match.\n            res.push_back(j++);\n        }\n\n        if (res.size() < pttr.length())\n            res.resize(0); // full length match not found => clear\n        return  res;\n    }\n};\n```
['C++']