Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s&nbsp;palindrome.

A&nbsp;Palindrome String&nbsp;is one that reads the same backward as well as forward.

&nbsp;
Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.


Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".


Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 500
	s consists of lowercase English letters.


class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        prev_prev = [0]*n
        prev = [0]*n
        curr = [0] * n

        for l in range(1, n):
            for i in range(l, n):
                if s[i] == s[i-l]:
                    curr[i] = prev_prev[i-1]
                else:
                    curr[i] = min(prev[i-1], prev[i])+1
            # print(curr)
            prev_prev, prev, curr = prev, curr, prev_prev
        
        return prev[-1]
class Solution {
    public int minInsertions(String s) {
        StringBuilder sb = new StringBuilder(s);
         String str = sb.reverse().toString();
        int m=s.length();
        int n=str.length();
         System.out.println(str);
        return LCS(s,str,m,n);

    }
    public int LCS(String x, String y,int m,int n){
        int [][] t = new int [m+1][n+1];
        for(int i=0;i<m+1;i++){
           for(int j=0;j<n+1;j++){
            if(m==0||n==0){t[m][n]=0;}
           }
        }
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                if(x.charAt(i-1)==y.charAt(j-1)){
                    t[i][j]=1+t[i-1][j-1];
                }
                else{t[i][j]=Math.max(t[i][j-1],t[i-1][j]);
                }
            }
        }
        return y.length()-t[m][n];
    }
}
class Solution {
public:
    int t[501][501];
    int MinInsertion(string x,int m){
    string y=x;
    reverse(y.begin(),y.end());
    for(int i=0;i<m+1;i++){
        for(int j=0;j<m+1;j++){
            if(i==0||j==0)
                t[i][j]=0;
        }
    }
    for(int i=1;i<m+1;i++){
        for(int j=1;j<m+1;j++){
            if(x[i-1]==y[j-1])
                t[i][j]=1+t[i-1][j-1];
            else    
                t[i][j]=max(t[i-1][j],t[i][j-1]);
        }
    }
    return m-t[m][m];
}
    int minInsertions(string s) {
        return MinInsertion(s,s.length());
    }
};
var minInsertions = function(s) {
    const len = s.length;
    const dp = new Array(len).fill(0).map(() => {
        return new Array(len).fill(-1);
    });

    const compute = (i = 0, j = len - 1) => {
        if(i >= j) return 0;

        if(dp[i][j] != -1) return dp[i][j];

        if(s[i] == s[j]) return compute(i + 1, j - 1);

        return dp[i][j] = Math.min(
            compute(i + 1, j),
            compute(i, j - 1)
        ) + 1;
    }
    return compute();
};
Minimum Insertion Steps to Make a String Palindrome