✅ [C++, Java, Python] Easy to understand | O(n^2) time and O(n) space | bottom up DP
Minimum Insertion Steps to Make a String Palindrome = Length of string - Length of longest palindromic subsequence.  \n\nC++ implementation:\n\nclass Solution {
Minimum Insertion Steps to Make a String Palindrome = Length of string - Length of longest palindromic subsequence.  \n\nC++ implementation:\n```\nclass Solution {\nprivate:\n    int findLCS(string &s1, string &s2) {\n        int n = s1.size();\n        vector<int> dp(n + 1, 0);\n        for(int i = 1; i <= n; ++i) {\n            vector<int> current(n + 1, 0);\n            for(int j = 1; j <= n; ++j) {\n                // match\n                if(s1[i - 1] == s2[j - 1])\n                    current[j] = 1 + dp[j - 1];\n                // not a match\n                else \n                    current[j] = max(dp[j], current[j - 1]);\n            }\n            dp = current;\n        }\n        return dp[n];\n    }\npublic:\n    int minInsertions(string &s1) {\n        string s2 = s1;\n        reverse(s2.begin(), s2.end());\n        return s1.size() - findLCS(s1, s2);\n    }\n};\n```\n\nJava implementation:\n\n```\nclass Solution {\n    private int findLCS(String s, String reverse) {\n        int n = s.length();\n        int[] dp = new int[n + 1];\n        for(int i = 1; i <= n; ++i) {\n            int[] current = new int[n + 1];\n            for(int j = 1; j <= n; ++j) {\n                if(s.charAt(i - 1) == reverse.charAt(j - 1))\n                    current[j] = 1 + dp[j - 1];\n                else\n                    current[j] = Math.max(dp[j], current[j - 1]);\n            }\n            dp = current;\n        }\n        return dp[n];\n    }\n    \n    public int minInsertions(String s) {\n        String reverse = new StringBuilder(s).reverse().toString();\n        return s.length() - findLCS(s, reverse);\n    }\n}\n```\n\nPython implementation:\n\n```\nclass Solution:\n    def findLCS(self, s: str, reverse: str) -> int:\n        n = len(s)\n        dp = [0] * (n + 1)\n        for i in range(1, n + 1):\n            current = [0] * (n + 1)\n            for j in range(1, n + 1):\n                # match\n                if s[i - 1] == reverse[j - 1]:\n                    current[j] = 1 + dp[j - 1]\n                else:\n                    current[j] = max(dp[j], current[j - 1])\n            dp = current\n        return dp[n]\n    \n    def minInsertions(self, s: str) -> int:\n        # using slicing to reverse a string\n        reverse = s[::-1]\n        return len(s) - self.findLCS(s, reverse)\n```\n\nTime complexity: O(n^2)\nSpace-complexity: O(n)\n\n\u23E9Thanks for reading! An upvote would be appreciated.  ^_^
['Dynamic Programming', 'C', 'Python', 'C++', 'Java']