Greedy Approach Time: O(n), Space: O(n+m)
Intuition\n Describe your first thoughts on how to solve this problem. \nWe put index in result even if character are not equal (skip) only when we are sure tha
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe put index in result even if character are not equal (skip) only when we are sure that we can obtain rest of the character as any subsequence from the further remaining characters in word1 string.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n+m)$$\n# Code\n```java []\nclass Solution {\n    public int[] validSequence(String w1, String w2) {\n        int n = w1.length(), m = w2.length();\n        int[] res = new int[m], last = new int[n];\n        for(int i = n - 1, index = m - 1; i >= 0; i--) {\n            if(index >= 0 && w1.charAt(i) == w2.charAt(index)) index--;\n            last[i] = m - index - 1;\n        }\n        boolean skip = false;\n        for(int i = 0, index = 0; i <= n; i++) {\n            if(index == m || i == n) return index == m ? res : new int[] {};\n            if(w1.charAt(i) == w2.charAt(index)) res[index++] = i;\n            else if(!skip && (i == n - 1 || last[i+1] >= m - index - 1) && (skip = true)) res[index++] = i;\n        }\n        return new int[] {}; \n    }\n}\n```
['Two Pointers', 'Greedy', 'Java']