class Solution {
public:
    int minCut(string s) 
    {     
        int n=s.length();        
        
        int* pali1=new int[n+1];
        int* pali2=new int[n+1];
        //1  3 5
        for(int i=0;i<n;i++) pali1[i]=1;
        for(int len=3;len<=n;len=len+2)
            for(int l=len/2;l<=n-1-len/2;l++)
                if(pali1[l]==len-2 && s[l-len/2]==s[l+len/2])
                    pali1[l]=len;
        //0 2 4
        for(int i=0;i<n;i++) pali2[i]=0;
        for(int len=2;len<=n;len=len+2)
            for(int l=len/2-1;l<=n-1-len/2;l++)
                if(pali2[l]==len-2 && s[l+1-len/2]==s[l+len/2])
                    pali2[l]=len;
        int** cutcache=new int*[n];
        for(int i=0;i<n;i++)
        {
            cutcache[i]=new int[n];
            for(int j=0;j<n;j++) cutcache[i][j]=-1;
        }
        return mincut(cutcache,s,0,n-1,pali1,pali2);
    }
    int mincut(int** cutcache,const string& s,int l,int r,const int* pali1,const int* pali2)
    {
        if(cutcache[l][r]!=-1) return cutcache[l][r];
        if(l>=r) return 0;
        
        if(check(s,l,r,pali1,pali2)) 
        {
            cutcache[l][r]=0;
            return 0;
        }
        int cut=r-l+1;
        for(int i=l;i<r;i++)
        if(check(s,l,i,pali1,pali2))
        {
            int newcut=1+mincut(cutcache,s,i+1,r,pali1,pali2);
            if(newcut<cut) cut=newcut;
        }
        cutcache[l][r]=cut;
        
        return cut;
    }
    bool check(const string& s,int l,int r,const int* pali1,const int* pali2)
    {
        int len=r-l+1;
        int mid=(l+r)/2;
        if(len%2==1 && pali1[mid]>=len) return true;
        if(len%2==0 && pali2[mid]>=len) return true;
        return false;
    }
};