Bottom up DP, Best Solution, C++ , O(n)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nDynamic Programming Array: We use a DP array dp where dp[i] represents th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nDynamic Programming Array: We use a DP array dp where dp[i] represents the number of matching characters of s2 starting from index i in s1. The array is initialized with n + 1 elements (where n is the length of s1) to handle the base case easily.\n\nBackward Matching: We iterate through s1 in reverse order to fill the dp array. If characters at the current index of s1 and s2 match, we increment our count of matches and move to the next character in s2. This way, we get a count of how many characters of s2 can still be matched starting from any position in s1.\n\nFinding Valid Indices: We then iterate through s1 again, this time from the start. For each character in s1, we check:\n\nIf it matches the current character in s2, we add its index to the result.\nIf it doesn\'t match, we check if we can skip this character. If the remaining matches (tracked in the dp array) plus one is greater than the characters left to match in s2, we can skip this character.\nFinal Validation: If the size of the result indices does not equal the length of s2, we return an empty list, indicating that s2 cannot be formed with the allowed operations.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string s1, string s2) {\n        int n = s1.size();\n        int m = s2.size();\n        vector<int> ans;\n        vector<int> dp(n+1);\n        bool changed = 1;\n        int curIdx = m-1;\n        for(int i=n-1;i>=0;i--){\n            dp[i] = dp[i+1];\n            if(curIdx >=0 && s1[i] == s2[curIdx]){\n                curIdx--;\n                dp[i]++;\n            }\n        }\n        int j = 0;\n        for(int i=0;i<n && j<m;i++){\n            if(s1[i] == s2[j]){\n                ans.push_back(i);\n                j++;\n            }else if(dp[i+1] + 1 > m-j-1 && changed == 1){\n                ans.push_back(i);\n                changed = 0;\n                j++;\n            }\n        }\n        if(ans.size() != m){\n            return {};\n        }\n        return ans;\n    }\n};\n```
['C++']