java dp
create a dp array which represents from index i, the number of chars word1 can match in word2\nex. dp[1] = 3 means from word1 position 1 to the end of word1, we
create a dp array which represents from index i, the number of chars word1 can match in word2\nex. dp[1] = 3 means from word1 position 1 to the end of word1, we can match the last 3 charactors in word2\nafter having the dp arrary, we know that we can only skip the current unmatched charactor if:\n we haven\'t skipped any charactor yet (skip>0)\n and\nthe rest of word1 can match the rest of words (dp[i+1]>=n2-j-1)\nso we can loop word1 to find the earliest unmatched position we can skip\n```\nclass Solution {\n    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;\n        int[] dp = new int[n1+1];\n        int idx1 = n1-1, idx2 = n2-1;\n        while(idx1>=0){\n            dp[idx1] = dp[idx1+1];\n            if(idx2>=0 && arr1[idx1]==arr2[idx2]){\n                dp[idx1]++;\n                idx2--;\n            }\n            idx1--;\n        }\n        int[] res = new int[n2];\n        int i=0, j=0, skip=1;\n        while(i<n1 && j<n2){\n            if (arr1[i]==arr2[j] || skip>0 && dp[i+1]>=n2-j-1){\n                if(arr1[i]!=arr2[j])\n                    skip--;\n                res[j] = i;\n                i++;\n                j++;\n            } else\n                i++;\n        }\n        if(j<n2)\n            return new int[0];\n        return res;\n    }\n}
[]