Top-Down Approach (DP)
Intuition\n Describe your first thoughts on how to solve this problem. \nThis question is a variation of longest palindromic subsequence(Q.no- 516).\n# Approach
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis question is a **variation of longest palindromic subsequence**(Q.no- 516).\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFind the length of LCS of given string and it\'s reverse. The **difference of the length of string and the LCS will give minimum no. of insertions and deletion** in the string to make it a palindrome\n# Complexity\n- Time complexity: **O(n*n)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Space complexity: **O(n*n)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int LCS(string a,string b)\n    {\n        int n=a.size(),m=b.size();\n        int t[n+1][m+1];\n        for(int i=0;i<n+1;i++)\n            t[i][0]=0;\n        for(int j=0;j<m+1;j++)\n            t[0][j]=0;\n        for(int i=1;i<n+1;i++)\n            for(int j=1;j<m+1;j++)\n            {\n                if(a[i-1]==b[j-1])\n                    t[i][j]=1+t[i-1][j-1];\n                else\n                    t[i][j]=max(t[i-1][j],t[i][j-1]);\n            }\n        return t[n][m];\n\n    }\n    int minInsertions(string s) {\n        int l=s.size();\n        if(l==1)\n        return 0;\n        string sr;\n        sr.append(s);\n        reverse(s.begin(),s.end());\n        return l-LCS(s,sr);\n    }\n};\n```
['C++']