这是 LeetCode 2430. Maximum Deletions on a String（对字符串可执行的最大删除数）的 Java 解法。

题目理解

每次操作可以：
1. 删除整个字符串（计1次操作）
2. 如果字符串的前 `i` 个字符与接下来的 `i` 个字符相等（`1 <= i <= s.length / 2`），则删除前 `i` 个字符

目标是求最大操作次数。

核心思路：动态规划 + LCP（最长公共前缀）

`dp[i]`：从位置 `i` 开始删除到末尾，最多需要多少次操作。

状态转移：
- 基础情况：直接删除剩余全部字符串 → `dp[i] = 1`
- 枚举长度 `j`（`1 <= j <= (n-i)/2`），如果 `s[i..i+j-1] == s[i+j..i+2j-1]`，则可以删除前 `j` 个，然后继续从 `i+j` 删除：`dp[i] = max(dp[i], dp[i+j] + 1)`

关键优化：用 LCP（Longest Common Prefix）数组快速判断两个子串是否相等，避免 `O(j)` 的字符串比较。

`lcp[i][j]` 表示从 `s[i]` 和 `s[j]` 开始的最长公共前缀长度。递推：
- 如果 `s[i] == s[j]`，则 `lcp[i][j] = lcp[i+1][j+1] + 1`
- 否则 `lcp[i][j] = 0`

判断 `s[i..i+j-1] == s[i+j..i+2j-1]` 只需检查 `lcp[i][i+j] >= j`。

Java 代码

```java
class Solution {
    public int deleteString(String s) {
        int n = s.length();
        
        // lcp[i][j] = 从s[i]和s[j]开始的最长公共前缀长度
        int[][] lcp = new int[n + 1][n + 1];
        
        // 从右往左填LCP表（因为lcp[i][j]依赖lcp[i+1][j+1]）
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                }
            }
        }
        
        // dp[i] = 从位置i开始删除，最多需要多少次操作
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  // 至少可以直接删除全部
        
        // 从右往左填dp表
        for (int i = n - 1; i >= 0; i--) {
            // 枚举删除长度j，最多为剩余长度的一半
            for (int j = 1; j <= (n - i) / 2; j++) {
                // 如果s[i..i+j-1] == s[i+j..i+2j-1]
                if (lcp[i][i + j] >= j) {
                    dp[i] = Math.max(dp[i], dp[i + j] + 1);
                }
            }
        }
        
        return dp[0];
    }
}
```

复杂度分析

项目    复杂度    
时间    O(n²) — 填LCP表 O(n²)，DP转移 O(n²)    
空间    O(n²) — LCP数组需要 (n+1)² 的空间    

其中 `n <= 4000`，O(n²) 完全可以通过。

示例验证

输入：`s = "aaabaab"`

输出：`4`

过程：
1. 位置0，删1个"a"（因为 `s[0]=='a'` 等于 `s[1]=='a'`）→ 剩余 `"aabaab"`
2. 位置1，删3个"aab"（因为 `s[1..3]="aab"` 等于 `s[4..6]="aab"`）→ 剩余 `"aab"`
3. 位置4，删1个"a"（因为 `s[4]=='a'` 等于 `s[5]=='a'`）→ 剩余 `"ab"`
4. 位置5，全部删除 → 结束

共 4 次操作。