O(n) solution using Manacher's algorithm


#1
string preprocess(string s) {
    string ans="#";
    for (int i=0;i<s.length();++i) {
        ans.push_back(s[i]);
        ans.push_back('#');
    }
    return ans;
}

vector<int> manacher(string s) {
    vector<int> ans(s.length());
    for (int i=0;i<s.length();++i) ans[i]=i;
    s = preprocess(s);
    int n=s.length();
    int p[n]={0};
    int c=0, r=0;
    for (int i=0;i<n;++i) {
        if (i<r) p[i] = min(p[c-(i-c)],r-i);
        while(i-p[i]>0 && i+p[i]<n-1 && s[i-p[i]-1]==s[i+p[i]+1]) ++p[i];
        if (i+p[i]>r) {
            c=i;
            r=i+p[i];
        }
    }
    for (int i=1;i<n-1;++i) {
        int right=(i+p[i]-1)/2, left=(i-p[i])/2;
        ans[right]=min(ans[right],left);
    }
    return ans;
}

int Solution::minCut(string s) {
    int n=s.length();
    int dp[n];
    dp[0]=0;
    vector<int> a = manacher(s);
    for (int i=1;i<n;++i) {
        if (a[i]<i) {
            if (a[i]>0) dp[i] = min(dp[a[i]-1]+1,dp[i-1]+1);
            else dp[i]=0;
        }
        else dp[i]=dp[i-1]+1;
    }
    return dp[n-1];
}