Two-Pointer Technique with Prefix and Suffix Arrays for Subsequence Matching
Intuition\nThe goal is to find a sequence of indices in word1 that match the characters in word2 while allowing at most one character to be ignored from word1. 
# Intuition\nThe goal is to find a sequence of indices in word1 that match the characters in word2 while allowing at most one character to be ignored from word1. The approach involves tracking the first and last occurrences of each character in word2 within word1 using two auxiliary arrays: pref for the first match and suff for the last match. This helps in determining if word2 can be formed as a subsequence with one mismatch.\n\n# Approach\n1. Character Arrays: \n- Convert word1 and word2 into character vectors for easier indexing.\n2. Prefix and Suffix Arrays:\n- Prefix Array (pref): Build an array that records the first index in word1 where each character of word2 is found, starting from the left.\n- Suffix Array (suff): Construct an array that records the last index in word1 where each character of word2 is found, starting from the right.\n3. Matching Logic:\n- If the last index of pref is not equal to the length of word1, adjust pref to allow for one mismatch by examining gaps between matches.\n- Check if valid matches exist using the suff array to see if you can skip a character in word1 when needed. If valid indices are found, return them as the result.\n\n# Complexity\n- Time complexity:\nThe overall time complexity is O(n + m), where n is the length of word1 and m is the length of word2. This is because each character of both strings is processed in linear time to construct the prefix and suffix arrays.\n\n- Space complexity:\nThe space complexity is O(m) due to the two auxiliary arrays (pref and suff) that store indices for the characters of word2. The character vectors also take O(n + m) space, but the primary space consideration comes from the auxiliary arrays.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1,string word2) {\n        vector<char> s1(word1.begin(),word1.end()),s2(word2.begin(),word2.end());\n        int n=s1.size(),m=s2.size();\n        if(m==1) return {0};\n        vector<int> suff(m);\n        int idx=n-1;\n        for(int i=m-1;i>=0;--i)\n        {\n            while(idx>=0 && s1[idx]!=s2[i]) idx--;\n            suff[i]=idx;\n            idx=max(-1,idx-1);\n        }\n        vector<int> pref(m);\n        idx=0;\n        for(int i=0;i<m;++i)\n        {\n            while(idx<n && s1[idx]!=s2[i]) idx++;\n            pref[i]=idx;\n            idx=min(n,idx+1);\n        }\n        if(pref[m-1]!=n)\n        {\n            idx=m;\n            int start=0;\n            if(pref[0]!=0)\n            {\n                pref[0]=0;\n                idx=1;\n                start=1;\n            }\n            else\n            {\n                for(int i=1;i<m;++i)\n                {\n                    if(pref[i]>pref[i-1]+1)\n                    {\n                        pref[i]=pref[i-1]+1;\n                        idx=i+1;\n                        start=pref[i]+1;\n                        break;\n                    }\n                }\n            }\n            for(int i=idx;i<m;++i)\n            {\n                while(start<n && s1[start]!=s2[i]) start++;\n                pref[i]=start;\n                start=min(n,start+1);\n            }\n            return pref;\n        }\n        if(suff[1]>0)\n        {\n            vector<int> ans(m);\n            ans[0]=0;\n            idx=1;\n            for(int i=1;i<m;++i)\n            {\n                while(idx<n && s1[idx]!=s2[i]) idx++;\n                ans[i]=idx;\n                idx=min(n,idx+1);\n            }\n            return ans;\n        }\n        for(int i=2;i<m;++i)\n        {\n            if(pref[i-2]+1<suff[i])\n            {\n                vector<int> ans(m);\n                for(int j=0;j<=i-2;++j) ans[j]=pref[j];\n                ans[i-1]=ans[i-2]+1;\n                idx=ans[i-1]+1;\n                for(int j=i;j<m;++j)\n                {\n                    while(idx<n && s1[idx]!=s2[j]) idx++;\n                    ans[j]=idx;\n                    idx=min(n,idx+1);\n                }\n                return ans;\n            }\n        }\n        return {};\n    }\n};\n\n```
['C++']