Easy to understand cpp solution with space optimization(beats 99.68%)
Intuition and Approach
The basic idea is to run Longest palindrome sequence on the string and then subtract the value from the string length to find out which a
# Intuition and Approach
<!-- Describe your first thoughts on how to solve this problem. -->
- The basic idea is to run Longest palindrome sequence on the string and then subtract the value from the string length to find out which are need to duplicated and put in right place to make the string palindrome.
- The longest palindrome sequence can be found by running LCS on string s and it's reverse.

# Complexity
- Time complexity: **O(n<sup>2</sup>)**
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: **O(n)**
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int minInsertions(string s) {
        string s1=s;
        reverse(s1.begin(),s1.end());
        int m=s.length();
        vector<int> prev(m+1),curr(m+1);
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                if(s[i-1]==s1[j-1]){
                    curr[j]=prev[j-1]+1;
                }
                else if(prev[j]>curr[j-1]){
                    curr[j]=prev[j];
                }
                else {
                    curr[j]=curr[j-1];
                }
            }
            prev=curr;
        }
        return s.length()-prev[m];
    }
};
```
['Dynamic Programming', 'C++']