# 2430. Maximum Deletions on a String
###### tags: `Leetcode` `Hard` `Dynamic Programming` `LCS`
Link: https://leetcode.com/problems/maximum-deletions-on-a-string/description/
## 思路

If ```lcs[i][j]=k```,
then ```s.substring(i, i+k) == s.substring(j, j+k)```
and ```s.substring(i, i+k+1) != s.substring(j, j+k+1)```
This can be done in ```O(n^2)```

the substring starting at ```s[i]```

If ```lcs[i][j] >= j-i```,

this means we can delete the prefix ```s.substring(i, j)``` from ```s.substring(i)```,
and it changes to ```s.substring(j)```.
And we update ```dp[i] = max(dp[i], dp[j]+1)```
## Code

class Solution {
public int deleteString(String s) {
int n = s.length();
int[][] lcs = new int[n+1][n+1];
for(int i=n-1; i>=0; i--){
for(int j=i+1; j<n; j++){
if(s.charAt(i)==s.charAt(j)){
lcs[i][j] = lcs[i+1][j+1]+1;
}
}
}
int[] dp = new int[n];
Arrays.fill(dp, 1);
for(int i=n-1; i>=0; i--){
for(int j=i+1; j<n; j++){
if(lcs[i][j]>=j-i) dp[i] = Math.max(dp[i], dp[j]+1);
}
}
return dp[0];
}
}