Python3 | C++| following problem hints.
Approach\ndp[i]= size of suffix of word2 which is subsequence of word1[i:]\n\nsmallest in lexicographic order is choosing the leftmost match/change for every ch
# Approach\ndp[i]= size of suffix of word2 which is subsequence of word1[i:]\n\nsmallest in lexicographic order is choosing the leftmost match/change for every char in word2.\n\ngreedily match leftmost chars in word1 to word2.\n`left_matches+1+dp[i+1]==len(word2)` implies we can change any char in `word1[last_matched_pos+1:i+1]` to make a valid subsequence.\n leftmost possible change is `last_matched_pos+1` so choose that.\ngreediy match for rest of word2 after finding changed index.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n# Code\n```python3 []\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        n = len(word1)\n        m = len(word2)\n\n        dp=[0]*(n+1)\n        for i in range(n-1,-1,-1):\n            dp[i]=dp[i+1]\n            if dp[i+1]<m and word1[i]==word2[m-dp[i+1]-1]:\n                dp[i]+=1\n        \n        ans=[]\n        free=True\n        for i in range(n):\n            if len(ans)==m:\n                break\n            if word1[i]==word2[len(ans)]:\n                ans.append(i)\n            elif free and len(ans)+1+dp[i+1]==m:\n                if len(ans)==0:\n                    ans.append(i)\n                else:\n                    ans.append(ans[-1]+1)\n                free=False\n        if len(ans)!=m:\n            return []\n        return ans\n```\n\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        int n=word1.size();\n        int m=word2.size();\n\n        vector<int>dp(n+1);\n        for(int i=n-1;i>=0;i--){\n            dp[i]=dp[i+1] + (dp[i+1]<m and word1[i]==word2[m-dp[i+1]-1]);       \n        }\n        \n        vector<int>ans;\n        bool free=1;\n        for(int i=0;i<n and ans.size()<m;i++){\n            if(word1[i]==word2[ans.size()])\n                ans.push_back(i);\n            else if(free and ans.size()+1+dp[i+1]>=m){\n                if(ans.size()==0)\n                    ans.push_back(i);\n                else\n                    ans.push_back(ans.back()+1);\n                free=0;\n            }\n        }\n\n        if(ans.size()!=m)\n            return {};\n        return ans;\n    }\n};\n```
['Greedy', 'C++', 'Python3']