Image Explanation🏆- [Recursion -> Top Down -> Bottom Up -> Bottom Up O(n)] - C++/Java/Python
Video Solution (Aryan Mittal) - Link in LeetCode Profile\nMinimum Insertion Steps to Make a String Palindrome by Aryan Mittal\n\n\n\n# Longest Palindromic Subse
# Video Solution (`Aryan Mittal`) - Link in LeetCode Profile\n`Minimum Insertion Steps to Make a String Palindrome` by `Aryan Mittal`\n![lc.png](https://assets.leetcode.com/users/images/049c3374-1bdd-4426-b961-2f988c034e8e_1682126946.7610044.png)\n\n\n# [Longest Palindromic Subsequence - LPS](https://leetcode.com/problems/longest-palindromic-subsequence/solutions/3415577/image-explanation-recursion-top-down-bottom-up-bottom-up-o-n/)\n![image.png](https://assets.leetcode.com/users/images/c4ca7c90-2cf9-4ed0-b9c9-5e1650e106d0_1682126076.4728723.png)\n\n# Approach & Intution\n![image.png](https://assets.leetcode.com/users/images/abe9efcd-bf18-4e39-ab1c-42c1c0cd68f7_1682126023.898669.png)\n![image.png](https://assets.leetcode.com/users/images/77262344-befb-4376-9907-8912d8707c03_1682126031.0959742.png)\n![image.png](https://assets.leetcode.com/users/images/65d0e4d0-d127-414f-aa4b-7e68db4cfbd6_1682126039.6311653.png)\n![image.png](https://assets.leetcode.com/users/images/98102f07-0275-45fa-a970-990cf93d4e14_1682126064.7054062.png)\n\n\n\n# Most Optimized DP Code:\n```C++ []\nclass Solution {\npublic:\n    int longestPalindromeSubseq(string& s) {\n        int n = s.size();\n        vector<int> dp(n), dpPrev(n);\n\n        for (int start = n - 1; start >= 0; --start) {\n            dp[start] = 1;\n            for (int end = start + 1; end < n; ++end) {\n                if (s[start] == s[end]) {\n                    dp[end] = dpPrev[end - 1] + 2;\n                } else {\n                    dp[end] = max(dpPrev[end], dp[end - 1]);\n                }\n            }\n            dpPrev = dp;\n        }\n\n        return dp[n - 1];\n    }\n\n    int minInsertions(string s) {\n        return s.length() - longestPalindromeSubseq(s);\n    }\n};\n```\n```Java []\nclass Solution {\n    public int longestPalindromeSubseq(String s) {\n        int n = s.length();\n        int[] dp = new int[n];\n        int[] dpPrev = new int[n];\n\n        for (int start = n - 1; start >= 0; --start) {\n            dp[start] = 1;\n            for (int end = start + 1; end < n; ++end) {\n                if (s.charAt(start) == s.charAt(end)) {\n                    dp[end] = dpPrev[end - 1] + 2;\n                } else {\n                    dp[end] = Math.max(dpPrev[end], dp[end - 1]);\n                }\n            }\n            dpPrev = dp.clone();\n        }\n\n        return dp[n - 1];\n    }\n\n    public int minInsertions(String s) {\n        return s.length() - longestPalindromeSubseq(s);\n    }\n}\n```\n```Python []\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        def longestPalindromeSubseq(self, s: str) -> int:\n            n = len(s)\n            dp = [0] * n\n            dpPrev = [0] * n\n\n            for start in range(n - 1, -1, -1):\n                dp[start] = 1\n                for end in range(start + 1, n):\n                    if s[start] == s[end]:\n                        dp[end] = dpPrev[end - 1] + 2\n                    else:\n                        dp[end] = max(dpPrev[end], dp[end - 1])\n                dpPrev = dp[:]\n\n            return dp[n - 1]\n\n        return len(s) - longestPalindromeSubseq(self, s)\n```\n\n
['String', 'Dynamic Programming', 'C++', 'Java', 'Python3']