给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：
- 删除 整个字符串
s ，或者
- 对于满足
1 <= i <= s.length / 2 的任意 i ，如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ，删除 前 i 个字母。
例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到 "abc" ，因为 s
的前两个字母和接下来的两个字母都等于 "ab" 。
返回删除 s 所需的最大操作数。
示例 1：
**输入：** s = "abcabcdabc"
**输出：** 2
**解释：**
- 删除前 3 个字母（"abc"），因为它们和接下来 3 个字母相等。现在，s = "abcdabc"。
- 删除全部字母。
一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。
注意，在第二步操作中无法再次删除 "abc" ，因为 "abc" 的下一次出现并不是位于接下来的 3 个字母。
示例 2：
**输入：** s = "aaabaab"
**输出：** 4
**解释：**
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "aabaab"。
- 删除前 3 个字母（"aab"），因为它们和接下来 3 个字母相等。现在，s = "aab"。
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "ab"。
- 删除全部字母。
一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。
示例 3：
**输入：** s = "aaaaa"
**输出：** 5
**解释：** 在每一步操作中，都可以仅删除 s 的第一个字母。
提示：
1 <= s.length <= 4000s 仅由小写英文字母组成
视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~
定义 f[i] 表示删除后缀 s[i:] 所需的最大操作数。
根据题意，我们可以枚举删除字母的长度 j，如果 s[i:i+j] = s[i+j:i+2j]，那么可以删除，此时有转移 f[i] = f[i+j] + 1。如果不存在两个子串相等的情况，则 f[i] = 1。f[i] 取所有情况的最大值。
倒着计算 f[i]，答案为 f[0]。
最后，我们需要快速判断两个子串是否相同。这可以用 O(n^2) 的 DP 预处理出来，具体见代码。
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def deleteString(self, s: str) -> int:
n = len(s)
if len(set(s)) == 1: return n
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(n - 1, i, -1):
if s[i] == s[j]:
lcp[i][j] = lcp[i + 1][j + 1] + 1
f = [0] * n
for i in range(n - 1, -1, -1):
for j in range(1, (n - i) // 2 + 1):
if lcp[i][i + j] >= j:
f[i] = max(f[i], f[i + j])
f[i] += 1
return f[0]
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int deleteString(String S) {
var s = S.toCharArray();
var n = s.length;
if (allEqual(s)) return n;
var lcp = new int[n + 1][n + 1];
for (var i = n - 1; i >= 0; --i)
for (var j = n - 1; j > i; --j)
if (s[i] == s[j])
lcp[i][j] = lcp[i + 1][j + 1] + 1;
var f = new int[n];
for (var i = n - 1; i >= 0; --i) {
for (var j = 1; i + j * 2 <= n; ++j)
if (lcp[i][i + j] >= j)
f[i] = Math.max(f[i], f[i + j]);
++f[i];
}
return f[0];
}
private boolean allEqual(char[] s) {
for (var i = 1; i < s.length; i++)
if (s[i] != s[0])
return false;
return true;
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int deleteString(string s) {
int n = s.length();
if (equal(s.begin() + 1, s.end(), s.begin()))
return n;
int lcp[n + 1][n + 1];
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;
int f[n];
memset(f, 0, sizeof(f));
for (int i = n - 1; i >= 0; --i) {
for (int j = 1; i + j * 2 <= n; ++j)
if (lcp[i][i + j] >= j)
f[i] = max(f[i], f[i + j]);
++f[i];
}
return f[0];
}
};
|
[sol1-Go]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| func deleteString(s string) int {
n := len(s)
if allEqual(s) {
return n
}
lcp := make([][]int, n+1)
lcp[n] = make([]int, n+1)
for i := n - 1; i >= 0; i-- {
lcp[i] = make([]int, n+1)
for j := n - 1; j > i; j-- {
if s[i] == s[j] {
lcp[i][j] = lcp[i+1][j+1] + 1
}
}
}
f := make([]int, n)
for i := n - 1; i >= 0; i-- {
for j := 1; i+j*2 <= n; j++ {
if lcp[i][i+j] >= j {
f[i] = max(f[i], f[i+j])
}
}
f[i]++
}
return f[0]
}
func allEqual(s string) bool {
for i := 1; i < len(s); i++ {
if s[i] != s[0] {
return false
}
}
return true
}
func max(a, b int) int { if b > a { return b }; return a }
|
复杂度分析
- 时间复杂度：O(n^2)，其中 n 为 s 的长度。
- 空间复杂度：O(n^2)。
