某口 313场周赛 对字母串可执行的最大删除数

https://leetcode.cn/problems/maximum-deletions-on-a-string/

思路：倒序二层遍历求 相同连续前缀字符串长度。 倒序算答案。

class Solution {
public:
    int deleteString(string s) {
        string t=s;
        sort(t.begin(),t.end());
        if( t[0]==t[t.size()-1] ) return s.size();
        int n=s.size();
        int lcp[n+1][n+1];
        int dp[n];
        memset(dp,0,sizeof(dp));
        memset(lcp,0,sizeof(lcp));
        for( int i=n-1;i>=0;i-- ){
            for( int j=n-1;j>i;j-- ){
                if( s[i]==s[j] ) lcp[i][j]=lcp[i+1][j+1]+1;
            }
        }
        for( int i=n-1;i>=0;i-- ){
            for( int j=1;i+2*j<=n;j++ ){
                if( lcp[i][j+i]>=j ) dp[i]=max(dp[i],dp[i+j]);
            }
            dp[i]+=1;
        }
        return dp[0];
    }
};