100% beat || O(n) || No DP || Simple traversing from end and then from front, and some observation.
\n\n# Complexity\n- Time complexity:\n Add your time complexity here, e.g. O(n) \nO(n)\n- Space complexity:\n Add your space complexity here, e.g. O(n) \nO(n)\n
![image.png](https://assets.leetcode.com/users/images/1a256633-ac18-4439-8d4e-50312e70bef5_1727553295.2699091.png)\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)$$\n# Code\n```java []\nclass Solution {\n    static public int[] validSequence(String word1, String word2) {\n        char[] arr1 = word1.toCharArray();\n        char[] arr2 = word2.toCharArray();\n        int n1 = arr1.length, n2 = arr2.length, ansIndex = -1;\n        if (n2 == 1) return new int[] { 0 };\n        int[] answer = new int[n2];\n        int[] temp = new int[n2];\n        Arrays.fill(temp, -1);\n        int last = -2, j = n2 - 1;\n        for (int i = n1 - 1; i >= 0 && j >= 0; i--) {\n            char ch = arr2[j];\n            if (ch == arr1[i]) {\n                last = i;\n                temp[j] = last;\n                j--;\n            }\n        }\n        if (j == -1) {\n            int a = 0, b = 0 , x = 0;\n            for (int i = 0; i < n1 && b < n2; i++) {\n                if (arr1[i] == arr2[b]) {\n                    a++;\n                    answer[x++] = i;\n                    b++;\n                } else  break;\n            }\n            a--;\n            if (x == n2) return answer;\n            answer[x++] = a+1;\n            int[] right = searchFor(word2.substring(a + 2), a + 2, arr1);\n            for (int i = 0; i < right.length; i++) answer[x++] = right[i];\n            return answer;\n        }\n        j = 0;\n        int i = 0;\n        if (ansIndex == -1 && temp[1] > 0) return youDoit(arr1, arr2);\n        for (i = 0; i < n1; i++) {\n            char ch = arr2[j];\n            if (ansIndex >= 0 && temp[ansIndex + 2] > answer[ansIndex] + 1) break;\n            if (ch == arr1[i]) {\n                answer[++ansIndex] = i;\n                j++;\n            }\n        }\n\n        if (i == n1) return new int[] {};\n\n        int[] right = searchFor(word2.substring(ansIndex + 2), answer[ansIndex] + 2, arr1);\n        answer[++ansIndex] = answer[ansIndex - 1] + 1;\n        \n        for (int k = 0; k < right.length; k++) answer[++ansIndex] = right[k];\n        return answer;\n    }\n\n    static int[] searchFor(String str, int from, char[] arr) {\n        char[] sarr = str.toCharArray();\n        int m = sarr.length;\n        int[] res = new int[m];\n        int x = 0, j = 0;\n        for (int i = from; i < arr.length && j < m; i++) {\n            char ch = sarr[j];\n            if (ch == arr[i]) {\n                res[x++] = i;\n                j++;\n            }\n        }\n        return res;\n    }\n\n    static int[] youDoit(char[] arr1, char[] arr2) {\n        int n1 = arr1.length, n2 = arr2.length, j = 1, x = 1;\n        int[] res = new int[n2];\n        for (int i = 1; i < n1 && j < n2; i++) {\n            char ch = arr2[j];\n            if (ch == arr1[i]) {\n                res[x++] = i;\n                j++;\n            }\n        }\n        res[0] = 0;\n        return res;\n    }\n}\n```
['Java']