JAVA || DP - 1D and 2D || Beats 70% Time & 100% Space || Explanation || Space optimization
Intuition\n Describe your first thoughts on how to solve this problem. \nTo make a given string palindrome, we need to insert some characters at some positions.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo make a given string palindrome, we need to insert some characters at some positions. If we can find out the longest common subsequence between the given string and its reverse, we can find out the characters that don\'t need to be inserted to make the string a palindrome. The number of insertions needed will be equal to the length of the given string minus the length of the longest common subsequence.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use dynamic programming to find the longest common subsequence between the given string `s` and its reverse. We can define a 2D array `dp` of size `(n+1)x(n+1)`, where `n` is the length of the string `s`. We can then populate the `dp` array using the following recurrence relation:\n\n```\nif s[i-1] == s_reverse[j-1]:\n    dp[i][j] = dp[i-1][j-1] + 1\nelse:\n    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n```\nOnce we have filled the `dp` array, we can return the difference between the length of `s` and the length of its longest common subsequence, which will give us the minimum number of insertions required to make `s` a palindrome.\n\nHowever, we can optimize the space complexity of our solution by using only a 1D array instead of a 2D array. We can define a 1D array `dp` of size `(n+1)`, where `n` is the length of the string `s`. We can then populate the `dp` array using the following recurrence relation:\n\n```\nif s[i-1] == s_reverse[j-1]:\n    dp[j] = prev + 1\nelse:\n    dp[j] = max(dp[j], dp[j-1])\n```\nHere, `prev` represents the value of `dp[j-1]` from the previous iteration of the inner loop.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n**O(n^2)** , where `n` is the length of the string `s`. This is because we need to fill the entire `dp` array, which has a size of `(n+1)x(n+1)`.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n**O(n)**, where `n` is the length of the string `s`. This is because we only need to use a 1D array of size `(n+1)` to store our dynamic programming table.\n\n# Code\n```\nclass Solution {\n    // Space optimized logic for the below code\n    public int minInsertions(String s) {\n        int n = s.length();\n        int[] dp = new int[n + 1];\n        int prev = 0;\n        for (int i = 1; i <= n; i++) {\n            prev = 0;\n            for (int j = 1; j <= n; j++) {\n                int temp = dp[j];\n                if (s.charAt(i - 1) == s.charAt(n - j)) {\n                    dp[j] = prev + 1;\n                } else {\n                    dp[j] = Math.max(dp[j], dp[j - 1]);\n                }\n                prev = temp;\n            }\n        }\n        return n - dp[n];\n    }\n    /*\n    2D array\n    public int minInsertions(String s) {\n        return s.length()-helper(s,reverse(s));        \n    }\n    private String reverse(String s)\n    {\n        String str = new StringBuilder(s).reverse().toString();\n        return str;\n    }\n    private int helper(String seedha, String ulta)\n    {\n        // Is function me hum longest common subsequence ka length nikalne wale hai\n        int n = seedha.length();\n        int[][] dp = new int[n+1][n+1];\n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<n;j++)\n            {\n                if(seedha.charAt(i) == ulta.charAt(j))\n                {\n                    dp[i+1][j+1]= dp[i][j]+1;\n                }\n                else\n                {\n                    dp[i+1][j+1]= Math.max(dp[i+1][j],dp[i][j+1]);\n                }\n            }\n        }\n        return dp[n][n];\n\n    }\n\n    */\n}\n```\n## If you found this helpful, please don\'t forget to upvote!\n
['String', 'Dynamic Programming', 'Java']