---
# System prepended metadata

title: 2430. Maximum Deletions on a String
tags: [Leetcode, Dynamic Programming, LCS, Hard]

---

# 2430. Maximum Deletions on a String
###### tags: `Leetcode` `Hard` `Dynamic Programming` `LCS`
Link: https://leetcode.com/problems/maximum-deletions-on-a-string/description/
## 思路
```lcs[i][j]``` means the length of the longest common substring.
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)```
```dp[i]``` mean the the maximum number of operations to delete
the substring starting at ```s[i]```

If ```lcs[i][j] >= j-i```,
```s.substring(i, j) == s.substring(j, 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
```java=
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];
    }
}
```