C++ Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nBasic idea was to check for the smallest index on which, after performing the operation
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBasic idea was to check for the smallest index on which, after performing the operation, remaining string will contain the pattern\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Firstly, iterate from the rear end of `string1` and keep checking at every index, upto which index of `string2`, from the back, you can find a matching subsequence. Store this in an array, say `v`.\n\n- for example lets say my strings are :\n```cpp\nstring1 = "aaabbccdd"\nstring2 = "cbd"\n```\n- for these strings, my array `v` would be :\n```cpp\nv = [ 1, 1, 1, 1, 1, 2, 2, 2, 2 ]\n```\n- In the above example, for index `i=5`, my `v[5]==2`, this means when my pointer on `string1` is currently at 5th index, i can find the pattern `string2[2:]` in `string1`, i.e., `"d"`.\n- similarly for `i=0`, my `v[0]==1`, which implies I can generate the subsequence `string2[1:]`, i.e., `"bd"`\n\n- Once you\'ve precomputed this, start iterating from the start of the `string1` and assume you have to find **completely identical sequence**. (simple two pointer approach using variables `i` for `string1` and `j` for `string2`).\n- At each index, where `string1[i] != string2[j]` , check if by replacing the current index `i` in `string1` with the character at `string2[j]`, I can complete the remaining part of `string2`, i.e., check if `v[i + 1] <= j + 1`. \n- If the condition satisfies, swapping at that particular index would return the lexographically smallest sequence of indices. (refer code below).\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string s1, string s2) {\n        int n = s1.size(), m = s2.size();\n        int j = m - 1;\n        vector<int> v(n, 0);\n        v.push_back(m);\n        \n        for (int i = n - 1; i >= 0; i--) {\n            v[i] = v[i + 1];\n            if (j >= 0 and s1[i] == s2[j]) {\n                v[i] = j;\n                j--;\n            }\n        }\n        \n        j = 0; \n        int swapind = -1;\n        \n        for (int i = 0; i < n; i++) {\n            if (s1[i] == s2[j]) {\n                j++;\n            } else if (v[i + 1] <= j + 1) {\n                swapind = j;\n                break;\n            }\n        }\n        \n        j = 0;\n        vector<int> ans;\n        \n        for (int i = 0; i < n and j < m; i++) {\n            if (j == swapind) {\n                ans.push_back(i);\n                j++;\n            } else if (s1[i] == s2[j]) {\n                ans.push_back(i);\n                j++;\n            }\n        }\n        \n        return (ans.size() < m ? vector<int>(0) : ans);\n    }\n};\n```
['C++']