<p>Given a string <code>s</code>, partition <code>s</code> such that every <span data-keyword="substring-nonempty">substring</span> of the partition is a <span data-keyword="palindrome-string">palindrome</span>.</p>

<p>Return <em>the <strong>minimum</strong> cuts needed for a palindrome partitioning of</em> <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aab&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> The palindrome partitioning [&quot;aa&quot;,&quot;b&quot;] could be produced using 1 cut.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;a&quot;
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ab&quot;
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> consists of lowercase English letters only.</li>
</ul>

class Solution {
public:
    typedef long long ll;
    vector <ll> manacher(string &s)
    {
        s = '#' + s + '#';
        ll n = s.size();
        vector <ll> p(n , 1); 
        ll l = 1, r = 1;
        for (ll i = 1; i < n; i++)
        {
            if(l+r-i>=0)
            p[i] = max(0ll, min(r - i, p[l + r - i]));
            while (i - p[i] >= 0 && i + p[i] < n && s[i - p[i]] == s[i + p[i]])
                p[i]++;
            if (i + p[i] > r)
            {
                l = i - p[i];
                r = i + p[i];
            }
        }
        return p;
    }
    ll rec(ll i,ll n,vector <ll> &p,vector <ll> &dp)
    {
        if(i==n)
        {
            return 0;
        }
        if(dp[i]!=-1)
        return dp[i];
        ll ret=1e9;
        for(ll j=i;j<n;j++)
        {
            ll len=j-i+1;
            if(len%2)
            {
                ll in=(j-(len/2));
                in=2*in+1;
                if(p[in]>len)
                {
                    ret=min(ret,1+rec(j+1,n,p,dp));
                }
            }
            else
            {
                ll in=(j-(len/2));
                in=2*in+2;
                if(p[in]>len)
                {
                    ret=min(ret,1+rec(j+1,n,p,dp));
                }
            }
        }
        return dp[i]=ret;
    }
    int minCut(string s) 
    {
        string t = "";
        for (ll i = 0; i < s.size(); i++)
        {
            if (i == s.size() - 1)
            {
                t += s[i];
            }
            else
            {
                t += (s[i]);
                t += '#';
            }
        }
        vector <ll> p = manacher(t);
        ll n=s.size();
        vector <ll> dp(n,-1);
        int ret=0;
        ret=rec(0,n,p,dp);
        return ret-1;
    }
};
9056