DP || TIME O(m*n),SPACE O(n) || C++
\nclass Solution {\npublic:\n    int minInsertions(string s1) {\n        int n = s1.length();\n        vector<int> dp1(n+1,0),dp2(n+1,0);\n        string s2 = s
````\nclass Solution {\npublic:\n    int minInsertions(string s1) {\n        int n = s1.length();\n        vector<int> dp1(n+1,0),dp2(n+1,0);\n        string s2 = s1;\n        reverse(s1.begin(),s1.end());\n        int i,j;\n        for(i = 1; i <= n; i++){\n            for(j = 1; j <= n; j++){\n                if(s1[i-1]==s2[j-1]){\n                    dp2[j] = dp1[j-1]+1;\n                }else{\n                    dp2[j] = max(dp1[j],dp2[j-1]);\n                }\n            }\n            dp1 =  dp2;\n        }\n        return n-dp1[n];\n    }\n};\n````
['Dynamic Programming', 'C', 'C++']