class Solution {
public:
int deleteString(string s) {
}
};
2430. 对字母串可执行的最大删除数
给你一个仅由小写英文字母组成的字符串 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 仅由小写英文字母组成原站题解
java 解法, 执行用时: 117 ms, 内存消耗: 213.8 MB, 提交时间: 2023-08-24 14:24:05
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]; // lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀
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) // 说明 s[i:i+j] == s[i+j:i+j*2]
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;
}
}
cpp 解法, 执行用时: 216 ms, 内存消耗: 75 MB, 提交时间: 2023-08-24 14:23:34
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]; // lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀
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) // 说明 s[i:i+j] == s[i+j:i+j*2]
f[i] = max(f[i], f[i + j]);
++f[i];
}
return f[0];
}
};
golang 解法, 执行用时: 112 ms, 内存消耗: 193.9 MB, 提交时间: 2023-08-24 14:23:07
func deleteString(s string) int {
n := len(s)
if allEqual(s) { // 特判全部相同的情况
return n
}
lcp := make([][]int, n+1) // lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀
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 { // 说明 s[i:i+j] == s[i+j:i+j*2]
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 }
python3 解法, 执行用时: 5712 ms, 内存消耗: 324.8 MB, 提交时间: 2023-08-24 14:22:40
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)] # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀
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: # 说明 s[i:i+j] == s[i+j:i+2*j]
f[i] = max(f[i], f[i + j])
f[i] += 1
return f[0]