Java || Prefix Sum || Not So easy Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\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\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int[] validSequence(String word1, String word2) {\n        final int n = word1.length();\n        final int m = word2.length();\n        final int[] ans = new int[m];\n        final int[] pref = new int[n];\n\n        if (m == 1) return new int[]{0};\n\n        for (int i = n - 1, j = m - 1; i >= 0; i--) {\n            pref[i] = i + 1 < n ? pref[i + 1] : 0;\n\n            if (j >= 0 && word1.charAt(i) == word2.charAt(j)) {\n                pref[i]++;\n                j--;\n            }\n        }\n\n        // System.out.println(Arrays.toString(pref));\n\n        int j = 0, tempInd = -1;\n\n        for (int i = 0; i < n && j < m; i++) {\n            if (word1.charAt(i) != word2.charAt(j)) {\n                if (tempInd == -1) tempInd = i;\n                if (j + 1 == m || (i + 1 < n && j + 1 < m && pref[i + 1] >= (m - (j + 1)))) break;\n            } else {\n                ans[j] = i;\n                tempInd = -1;\n                j++;\n            }\n        }\n\n        if (j == m) return ans;\n        if (tempInd == -1) return new int[0];\n\n        ans[j++] = tempInd++;\n\n        // System.out.println(Arrays.toString(ans));\n\n        if (pref[tempInd] < (m - j)) return new int[0];\n\n        for (int i = tempInd, k = j; i < n && k < m; i++) {\n            if (word1.charAt(i) == word2.charAt(k)) {\n                ans[k++] = i;\n            }\n        }\n\n        return ans;\n    }\n}\n```
['Java']