对字母串可执行的最大删除数

难度: Hard

给你一个仅由小写英文字母组成的字符串 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 <= 4000
s 仅由小写英文字母组成

Submission

运行时间: 3642 ms

内存: 317.5 MB

class Solution:
    """
    f(i) => 删除后缀s[i:]所需要的最大删除次数

    if s[i:i+j] == s[i+j:i+2j] do
        f(i) = f(i+j) + 1
    else
        f(i) = 1
    end

    ans = f(0)
    """

    def deleteString(self, s: str) -> int:
        n = len(s)
        if len(set(s)) == 1:
            return n  # 全部相同，直接删除到空串

        # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀
        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(i) => 删除后缀s[i:]所需要的最大删除次数
        f = [0] * n
        for i in range(n - 1, -1, -1):
            for j in range(1, (n - i) // 2 + 1):
                # s[i:]和s[i+j:]的最长公共前缀长度大于等于j => s[i:i+j] == s[i+j:i+2j]
                if lcp[i][i + j] >= j:
                    f[i] = max(f[i], f[i + j])
            f[i] += 1
        return f[0]

Explain

此题解采用动态规划的方法解决问题。定义一个数组 f，其中 f[i] 表示从字符串的第 i 个字符开始到结束所有可能的删除操作的最大数目。具体过程中，先计算字符串任意两个后缀的最长公共前缀（LCP），存储在二维数组 lcp 中。然后使用这个 lcp 数组来快速判断任意两个相等长度的子串是否相等。对于每个位置 i，检查所有可能的 j（长度为从 1 到 (n-i)/2 的子串），如果 s[i:i+j] 等于 s[i+j:i+2j]，则尝试更新 f[i] 为 f[i+j]+1 的最大值。最终，f[0] 即为整个字符串 s 的最大删除次数。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

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]  # 返回从头开始删除的最大次数

Explore

在动态规划解法中，f数组的初始值被设为0，这意味着每个位置至少可以删除一次（即它自身）。更新规则基于判断能否删除连续重复的子串。当发现某个子串可以被重复且连续删除时（即子串相等），f[i]会更新为f[i+j]加上当前这一次删除操作。这样，f[i]代表从位置i开始，所能执行的最大删除操作数。

从后向前计算LCP数组可以有效利用已知的LCP值来简化计算。当我们知道s[i+1]到s[j+1]的LCP时，可以轻易推出s[i]到s[j]的LCP，只需检查s[i]是否等于s[j]。这种方法减少了重复的比较和计算，提高了效率。

当i或j接近字符串末尾时，LCP的计算需要确保不会越界。因此，在初始化LCP数组时，所有的边界值（特别是当i或j等于字符串长度n时）都被设为0。这是因为超出字符串长度的部分没有字符，所以公共前缀长度为零。在LCP的递推计算中，只有当s[i]和s[j]相等且它们的位置都在字符串长度内时，才会基于s[i+1]和s[j+1]的LCP值进行更新。

在更新f数组时，利用lcp数组来快速判断两个子串是否相等。具体的判断条件是检查lcp[i][i+j]是否大于等于j。这表示s[i:i+j]与s[i+j:i+2j]的最长公共前缀长度至少为j，即这两个子串完全相同。因此，如果这个条件成立，我们可以认为从i开始的子串可以执行一次删除操作（删除s[i:i+j]），然后从i+j位置继续尝试删除。