C++ | Clean Code (25 lines) | Easy to understand | Well explained
\n## Pls upvote the thread if you found it helpful.\n\n# Intuition\n Describe your first thoughts on how to solve this problem.l  \nIn order to minimize the ins
\n## **Pls upvote the thread if you found it helpful.**\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem.l --> \nIn order to minimize the insertions, we need to find the **difference** of length of the longest palindromic subsequence and string length. \n\n`Minimum Insertion required = len(string) \u2013 length(lps)`\n\n**This question has a pre req : [Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/)**\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- We are given a string, store its length as n.\n- Find the length of the longest palindromic subsequence (say l) \n- Return n-l as answer.\n\n# Complexity\n- Time complexity: O(N*M) two nested loops\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(M) external array of size \u2018M+1\u2019 to store only two rows\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\nprivate:\n    int lcs(string s1, string s2) {\n    int n = s1.size();\n    int m = s2.size();\n    vector<int> prev(m + 1,0), cur(m + 1,0);\n    for(int ind1 = 1;ind1 <= n; ind1++){\n        for(int ind2 = 1;ind2 <= m;ind2++){\n            if(s1[ind1 - 1] == s2[ind2 - 1])\n                cur[ind2] = 1 + prev[ind2 - 1];\n            else\n                cur[ind2] = 0 + max(prev[ind2],cur[ind2 - 1]);\n        }\n        prev = cur;\n    }\n    return prev[m];\n}\n        int longestPalindromeSubsequence(string s){\n        string t = s;\n        reverse(s.begin(),s.end());\n        return lcs(s,t);\n    }\npublic:   \n    int minInsertions(string s) {\n        int n = s.size();\n        int k = longestPalindromeSubsequence(s);\n        return n-k;\n    }\n};\n```
['String', 'Dynamic Programming', 'C', 'C++']