Greedy Solution || C++ Solution
Intuition\nThe goal is to find whether word2 is a subsequence of word1 and return the indices in word1 where the characters of word2 appear in order. A subseque
# Intuition\nThe goal is to find whether word2 is a subsequence of word1 and return the indices in word1 where the characters of word2 appear in order. A subsequence means the characters must appear in the same order, but not necessarily consecutively. The idea is to iterate through word1 and try to match the characters of word2. If at any point it seems like further characters can form the subsequence, use a helper function (solve) to verify and extract the remaining indices.\n\n# Approach\n**Suffix Array Construction:**\nThe suffix array is built from the end of word1 to determine how many characters of word2 can be matched from the current position onwards in word1. This helps decide if it\'s worth continuing to match or using the helper function to attempt completion of the subsequence.\n\n**Main Loop:**\nTraverse word1 from left to right, matching characters of word2.\nIf characters match, push the current index into the ans vector.\nIf a mismatch is encountered but the suffix array indicates that the remaining part of word1 could potentially match word2, call the solve function to attempt completion of the subsequence.\n\n**Helper Function solve:**\nThis function continues matching the remaining characters of word2 from a certain point in word1.\nIt pushes the indices of matching characters into the ans vector.\n\n**Final Check:**\nAfter the loop, if the size of the ans vector is equal to the length of word2, it means a valid subsequence has been found; otherwise, return an empty vector indicating failure.\n\n# Complexity\n- Time complexity:\nThe time complexity is dominated by the single traversal of word1 and the occasional use of the solve function. Thus, the overall complexity is: O(m), where m is the length of word1.\n\n- Space complexity: O(m), for storing the suffix array and the result vector.\n# Code\n```cpp []\nclass Solution {\npublic:\n    void solve(string s1, string s2, int i, int j, vector<int>& ans) {\n        for (int k = i; k < s1.length() && j < s2.length(); k++) {\n            if (s1[k] == s2[j]) {\n                ans.push_back(k);\n                j++;\n            }\n        }\n\n        return;\n    }\n    vector<int> validSequence(string word1, string word2) {\n        int m = word1.size();\n        int n = word2.size();\n\n        if (n > m)\n            return {};\n\n        vector<int> suffix(m + 1, 0);\n        int k = n - 1;\n        int cnt = 0;\n\n        for (int j = m - 1; j >= 0; j--) {\n            if (k >= 0 && word1[j] == word2[k]) {\n                cnt++;\n                k--;\n            }\n            suffix[j] = cnt;\n        }\n        vector<int> ans;\n        k = 0;\n        vector<int> temp;\n        for (int i = 0; i < m; i++) {\n            if (k < n && word1[i] == word2[k]) {\n                ans.push_back(i);\n                k++;\n            } else if (suffix[i + 1] + k >= n - 1) {\n                ans.push_back(i);\n                solve(word1, word2, i + 1, k+1, ans);\n                break;\n            }\n            if (ans.size() == n)\n                break;\n        }\n        if (ans.size() != n)\n            return {};\n\n        return ans;\n    }\n};\n\n```
['C++']