Find-the-lexicographically-smallest-valid-sequence✅☑[JAVA] || O(2N)|| Optimal Solution
\n# Complexity\n- Time complexity:O(N)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(N)\n Add your space complexity here, e.g. O(n) \n\n# 
\n# Complexity\n- Time complexity:O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\n// import java.util.ArrayList;\n\n// class Solution {\n//     public int[] validSequence(String word1, String word2) {\n//         int n = word1.length();\n//         int m = word2.length();\n//         int[] dp = new int[n + 1];\n//         dp[n] = 0;  // Initialize the dp array for suffix matching\n\n//         int i = n - 1, j = m - 1;\n\n//         // Fill dp array with max suffix lengths\n//         while (i >= 0 && j >= 0) {\n//             if (word1.charAt(i) == word2.charAt(j)) {\n//                 dp[i] = (m - j);  // Record suffix length that matches\n//                 i--;\n//                 j--;\n//             } else {\n//                 i--;\n//             }\n//         }\n\n//         // Ensure that dp[i] holds the maximum suffix length from any i onwards\n//         for (i = n - 2; i >= 0; i--) {\n//             dp[i] = Math.max(dp[i], dp[i + 1]);\n//         }return dp;\n\n//         // ArrayList<Integer> list = new ArrayList<>();\n//         // int a = 0, b = 0;\n//         // boolean flagUsed = false;\n\n//         // // Build the list of valid indices\n//         // while (a < n && b < m) {\n//         //     if (word1.charAt(a) == word2.charAt(b)) {\n//         //         list.add(a);  // Direct match, so add the index\n//         //         a++;\n//         //         b++;\n//         //     } else {\n//         //         // Check if we can include a character at `a` to match the suffix\n//         //         int remainingLength = m - b - 1;\n//         //         if (!flagUsed && dp[a + 1] >= remainingLength) {\n//         //             list.add(a);\n//         //             flagUsed = true;  // Use the flag once\n//         //             a++;\n//         //             b++;\n//         //         } else {\n//         //             a++;\n//         //         }\n//         //     }\n//         // }\n\n//         // // Convert ArrayList to an array\n//         // int[] ans = new int[list.size()];\n//         // for (int k = 0; k < list.size(); k++) {\n//         //     ans[k] = list.get(k);\n//         // }\n\n//         // // Return the result only if it matches the size of word2\n//         // return (list.size() == m) ? ans : new int[0];\n//     }\n// }\n\n\nclass Solution {\n    public int[] validSequence(String word1, String word2) {\n        int dp[]=new int[word1.length()+1];\n        dp[dp.length-1]=0;\n        int n=word1.length();\n        int m=word2.length();\n        int i=n-1;\n        int j=m-1;\n        int count=0;\n        while(i>=0 && j>-1){\n            \n          if(word1.charAt(i)==word2.charAt(j)){\n            \n                count++;\n                dp[i]=count;\n                i--;\n                j--;\n            }else {\n                dp[i]=count;\n                i--;\n            }\n        }\n        int p=dp.length-1;;\n        int max=0;\n     while(p>=0){\n        max=Math.max(max,dp[p]);\n        dp[p]=max;\n        p--;\n     }\n\n        int a=0;\n        int b=0;\n        int flag=0;\n        ArrayList<Integer>list=new ArrayList<>();\n        \n        while(a<n && b<m){\n            if(word1.charAt(a)==word2.charAt(b)){\n                list.add(a);\n                a++;\n                b++;\n            }else{\n            if(flag==0 && m-b-1<=dp[a+1]){\n                list.add(a);\n                flag=1;\n                a++;\n                b++;\n            }else  {\n                 a++;\n            }\n            }\n        }\n\n        int ans[]=new int[list.size()];\n        \n            for(int k=0;k<list.size();k++){\n                ans[k]=list.get(k);\n            }\n        if(list.size()==m)return ans;\n        else return new int[0] ;\n\n\n    }\n}\n```
['Math', 'Dynamic Programming', 'Java']