"Palindrome Perfection: Efficient Dynamic Programming for Minimum Insertions" || Same as 516. LPS✔️
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the minimum number of insertions needed to make a given st
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the minimum number of insertions needed to make a given string a palindrome. This can be approached by leveraging the concept of the Longest Common Subsequence (LCS).\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe key idea is to find the length of the Longest Palindromic Subsequence (LPS) in the given string. The difference between the string\'s length and the LPS length gives the minimum number of insertions needed. Here\'s the step-by-step approach:\n\n- Reverse the String:\nCreate a reversed version of the input string. The LCS of the string and its reverse will give the LPS of the string.\n\n- Dynamic Programming Setup:\nCreate a 2D DP array dp where dp[i][j] represents the length of the LCS of the first i characters of the original string and the first j characters of the reversed string.\n\n- DP Array Initialization and Filling:\nInitialize the DP array with zeros.\nIterate through the characters of both the original and reversed strings:\n-If characters match, increment the LCS length by 1.\n-If characters don\'t match, take the maximum LCS length by either excluding the current character of the original string or the reversed string.\n\n- Calculate Result:\nThe length of the LPS is found at dp[s.length()][s.length()].\nThe minimum number of insertions required is the difference between the string length and the LPS length.\n\n# Complexity\n- Time complexity: O(N2)\nWe use nested loops to fill the DP array, where \uD835\uDC41 is the length of the string.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N2)\nThe space is used for the 2D DP array.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int minInsertions(String s) {\n        String s2 = new StringBuilder(s).reverse().toString();\n        int[][] dp = new int[s.length()+1][s.length()+1];\n\n        for(int i = 1;i<=s.length();i++){\n            for(int j = 1;j<=s.length();j++){\n                if(s.charAt(i-1) == s2.charAt(j-1))dp[i][j] = 1 + dp[i-1][j-1];\n                else{\n                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);\n                }\n            }\n        }\n        return s.length()-dp[s.length()][s.length()];\n    }\n}\n```
['String', 'Dynamic Programming', 'Java']