3302. Find the Lexicographically Smallest Valid Sequence
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 []\nimport java.util.Arrays;\n\nclass Solution {\n    public int[] validSequence(String word1, String word2) {\n        int m = word1.length();\n        int n = word2.length();\n        int[] dp = new int[n];\n        Arrays.fill(dp, -1);\n        int j = n - 1;\n        for (int i = m - 1; i >= 0; i--) {\n            if (j < 0) {\n                break;\n            }\n            if (word1.charAt(i) == word2.charAt(j)) {\n                dp[j--] = i;\n            }\n        }\n        int[] result = new int[n];\n        boolean mismatch = true;\n        j = 0;\n        for (int i = 0; i < m; i++) {\n            if (j == n) {\n                break;\n            }\n            if (word1.charAt(i) == word2.charAt(j)) {\n                result[j++] = i;\n            } else if (mismatch && (j == n - 1 || dp[j + 1] > i)) {\n                mismatch = false;\n                result[j++] = i;\n            }\n        }\n        return j == n ? result : new int[0];\n    }\n}\n```
['Java']