✔️✔️Easy Solutions in Java ✔️✔️, Python ✔️, and C++ ✔️🧐Look at once 💻 with Exaplanation
Intuition\n Describe your first thoughts on how to solve this problem. \n>To make a given string s a palindrome, we need to insert characters at some positions 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n>To make a given string `s` a palindrome, we need to insert characters at some positions in the string. If we can find the longest common subsequence (LCS) between the given string `s` and its reverse, we can find the characters that are already part of the palindrome. Then, we can insert the remaining characters (which are not part of the LCS) at their appropriate positions in the string to make it a palindrome.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Reverse the input string to get a new string `reversed_s`.\n2. Initialize a 2D array `dp` of size `(n+1)x(n+1)` with 0s, where `n` is the length of the input string `s`.\n3. Iterate through all pairs of indices `(i,j)` of the array `dp`, where `1<=i,j<=n`.\n4. If the characters at indices `i-1` in string `s` and `j-1` in `reversed_s` are equal, set `dp[i][j] = dp[i-1][j-1] + 1`.\n5. Otherwise, set `dp[i][j]` to the maximum of `dp[i-1][j]` and `dp[i][j-1]`.\n6. The length of the LCS between `s` and `reversed_s` is `dp[n][n]`.\n7. The minimum number of insertions required to make `s` a palindrome is `n - dp[n][n]`\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 input string `s`. This is because we are filling up a 2D array of size `(n+1)x(n+1)` using dynamic programming approach.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n>O(n^2), where `n` is the length of the input string `s`. This is because we are using a 2D array of size `(n+1)x(n+1)` to store the LCS of substrings.\n\n\n![image.png](https://assets.leetcode.com/users/images/b427e686-2e5d-469a-8e7a-db5140022a6b_1677715904.0948765.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n```\n\n\n# Code\n```java []\nclass Solution {\n    public int minInsertions(String s) {\n        // reverse the input string\n        String reversed = new StringBuilder(s).reverse().toString();\n        // get the length of the input string\n        int n = s.length();\n        // create a 2D array to store the LCS of substrings\n        int[][] dp = new int[n+1][n+1];\n        \n        // fill up the dp array using dynamic programming approach\n        for(int i=1; i<=n; i++) {\n            for(int j=1; j<=n; j++) {\n                if(s.charAt(i-1) == reversed.charAt(j-1)) {\n                    // if characters match, add 1 to LCS\n                    dp[i][j] = dp[i-1][j-1] + 1;\n                } else {\n                    // otherwise, take maximum LCS of two substrings\n                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);\n                }\n            }\n        }\n        \n        // return the minimum number of insertions required to make s a palindrome\n        // this is the difference between the length of s and the length of its LCS\n        return n - dp[n][n];\n    }\n}\n\n```\n```python []\nclass Solution(object):\n    def minInsertions(self, s):\n        # reverse the input string\n        reversed_s = s[::-1]\n        # get the length of the input string\n        n = len(s)\n        # create a 2D array to store the LCS of substrings\n        dp = [[0 for j in range(n+1)] for i in range(n+1)]\n        \n        # fill up the dp array using dynamic programming approach\n        for i in range(1, n+1):\n            for j in range(1, n+1):\n                if s[i-1] == reversed_s[j-1]:\n                    # if characters match, add 1 to LCS\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    # otherwise, take maximum LCS of two substrings\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n        \n        # return the minimum number of insertions required to make s a palindrome\n        # this is the difference between the length of s and the length of its LCS\n        return n - dp[n][n]\n```\n```C++ []\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        // reverse the input string\n        string reversed_s = string(s.rbegin(), s.rend());\n        // get the length of the input string\n        int n = s.length();\n        // create a 2D vector to store the LCS of substrings\n        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));\n        \n        // fill up the dp vector using dynamic programming approach\n        for(int i=1; i<=n; i++) {\n            for(int j=1; j<=n; j++) {\n                if(s[i-1] == reversed_s[j-1]) {\n                    // if characters match, add 1 to LCS\n                    dp[i][j] = dp[i-1][j-1] + 1;\n                } else {\n                    // otherwise, take maximum LCS of two substrings\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);\n                }\n            }\n        }\n        \n        // return the minimum number of insertions required to make s a palindrome\n        // this is the difference between the length of s and the length of its LCS\n        return n - dp[n][n];\n    }\n};\n```\n\n``` javascript []\n/**\n * @param {string} s\n * @return {number}\n */\nvar minInsertions = function(s) {\n    // reverse the input string\n    const reversedS = s.split(\'\').reverse().join(\'\');\n    // get the length of the input string\n    const n = s.length;\n    // create a 2D array to store the LCS of substrings\n    const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));\n    \n    // fill up the dp array using dynamic programming approach\n    for(let i = 1; i <= n; i++) {\n        for(let j = 1; j <= n; j++) {\n            if(s[i-1] === reversedS[j-1]) {\n                // if characters match, add 1 to LCS\n                dp[i][j] = dp[i-1][j-1] + 1;\n            } else {\n                // otherwise, take maximum LCS of two substrings\n                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);\n            }\n        }\n    }\n    \n    // return the minimum number of insertions required to make s a palindrome\n    // this is the difference between the length of s and the length of its LCS\n    return n - dp[n][n];\n};\n\n```\n```\nLCS stands for Longest Common Subsequence\n```\n\n# Please Comment\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution comment below if you like it.\uD83D\uDE0A\n```
['Dynamic Programming', 'Python', 'C++', 'Java', 'JavaScript']