class Solution {
public:
    int minInsertions(string s) {

        int n = (int)s.size();

        vector<vector<int>>dp(n, vector<int>(n));

// dp[i][j] : what is minimum no of insertion to make palindrome that starts with i and ends at j.

        for(int i=n-2;i>=0;i--){

            for(int j=i+1; j<n; j++){

                if(s[i] == s[j]){
                    dp[i][j] = dp[i+1][j-1];
                }
                else{
                    dp[i][j] = 1+min(dp[i][j-1], dp[i+1][j]);
                }
            }

        }

       // cout<<dp[0][n-1]<<"\n";
        return dp[0][n-1];
    }
};