R2L then L2R
Intuition\nThe idea is to first match, R2L, for each index, as many characters as possible, then sweep from L2R and do the same. For each index, if the total nu
# Intuition\nThe idea is to first match, R2L, for each index, as many characters as possible, then sweep from L2R and do the same. For each index, if the total number of characters from the left and right sides are >= N2 - 1, it means it\'s possible to use a wildcard at the index to make a valid sequence. It can also be shown at, using the left most found index would be the lexicographically smallest.\n\n# Code\n```java []\nclass Solution {\n    public int[] validSequence(String word1, String word2) {\n        int n1 = word1.length(), n2 = word2.length();\n        var right = new int[n1];\n        right[n1-1] = n2;\n        for(int i = n1-2; i > -1; i--) {\n            int k = right[i+1];\n            right[i] = k > 0 && word1.charAt(i+1) == word2.charAt(k-1) ? k - 1 : k;\n        }\n        var res = new int[n2];\n        int i = 0, j = 0;\n        for(; i < n1 && j < n2 && j + 1 < right[i]; i++) {\n            if(word1.charAt(i) == word2.charAt(j)) res[j++] = i;\n        }\n        if(i == n1) return new int[0];\n        for(boolean used = false; j < n2; i++) {\n            if(word1.charAt(i) == word2.charAt(j)) {\n                res[j++] = i;\n            } else if(!used) {\n                res[j++] = i;\n                used = true;\n            }\n        }\n        return res;\n    }\n}\n```
['Java']