Hard

题目描述

给你一个只包含小写英文字母的字符串 s。在一次操作中，你可以：

  • 删除整个字符串 s，或者
  • 删除字符串 s 的前 i 个字母，当且仅当前 i 个字母和接下来的 i 个字母相等，其中 1 <= i <= s.length / 2。

例如，如果 s = "ababc"，那么在一次操作中，你可以删除前两个字母得到 "abc"，因为前两个字母和接下来的两个字母都等于 "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 只包含小写英文字母

解题思路

这是一个动态规划问题。我们需要找到删除整个字符串所需的最大操作数。

核心思路：

  1. 状态定义：设 dp[i] 表示从位置 i 开始到字符串末尾所需的最大操作数。

  2. 状态转移：对于位置 i，我们有两种选择：

    • 直接删除剩余所有字符（1次操作）
    • 删除长度为 len 的前缀（如果前缀与后续相同长度的子串相等），然后递归处理剩余部分

  3. 子串比较优化：为了高效比较子串是否相等，我们可以使用滚动哈希或预计算所有子串的哈希值。

  4. 算法流程：

    • 从字符串末尾向前计算每个位置的 dp 值
    • 对于每个位置 i，尝试所有可能的删除长度 len（1 到 (n-i)/2）
    • 检查 s[i:i+len] 是否等于 s[i+len:i+2*len]
    • 如果相等，更新 dp[i] = max(dp[i], 1 + dp[i+len])

时间复杂度：使用哈希比较子串的时间复杂度为 O(n²)，其中 n 是字符串长度。

代码实现

class Solution {
public:
    int deleteString(string s) {
        int n = s.length();
        vector<int> dp(n + 1, 1);
        
        // 预计算所有子串是否相等
        vector<vector<bool>> equal(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    equal[i][j] = true;
                } else if (s[i] == s[j]) {
                    if (i + 1 < n && j + 1 < n) {
                        equal[i][j] = equal[i + 1][j + 1];
                    } else {
                        equal[i][j] = true;
                    }
                }
            }
        }
        
        for (int i = n - 1; i >= 0; i--) {
            for (int len = 1; len <= (n - i) / 2; len++) {
                if (equal[i][i + len]) {
                    dp[i] = max(dp[i], 1 + dp[i + len]);
                }
            }
        }
        
        return dp[0];
    }
};

class Solution:
    def deleteString(self, s: str) -> int:
        n = len(s)
        dp = [1] * (n + 1)
        
        # 预计算所有子串是否相等
        equal = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if i == j:
                    equal[i][j] = True
                elif s[i] == s[j]:
                    if i + 1 < n and j + 1 < n:
                        equal[i][j] = equal[i + 1][j + 1]
                    else:
                        equal[i][j] = True
        
        for i in range(n - 1, -1, -1):
            for length in range(1, (n - i) // 2 + 1):
                if equal[i][i + length]:
                    dp[i] = max(dp[i], 1 + dp[i + length])
        
        return dp[0]

public class Solution {
    public int DeleteString(string s) {
        int n = s.Length;
        int[] dp = new int[n + 1];
        Array.Fill(dp, 1);
        
        // 预计算所有子串是否相等
        bool[,] equal = new bool[n, n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    equal[i, j] = true;
                } else if (s[i] == s[j]) {
                    if (i + 1 < n && j + 1 < n) {
                        equal[i, j] = equal[i + 1, j + 1];
                    } else {
                        equal[i, j] = true;
                    }
                }
            }
        }
        
        for (int i = n - 1; i >= 0; i--) {
            for (int len = 1; len <= (n - i) / 2; len++) {
                if (equal[i, i + len]) {
                    dp[i] = Math.Max(dp[i], 1 + dp[i + len]);
                }
            }
        }
        
        return dp[0];
    }
}

var deleteString = function(s) {
    const n = s.length;
    const memo = new Map();
    
    function dp(start) {
        if (start >= n) return 0;
        if (memo.has(start)) return memo.get(start);
        
        let maxOps = 1; // Always can delete the entire remaining string
        
        // Try deleting first i characters if they match the next i characters
        const remaining = n - start;
        for (let i = 1; i <= Math.floor(remaining / 2); i++) {
            let match = true;
            for (let j = 0; j < i; j++) {
                if (s[start + j] !== s[start + i + j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                maxOps = Math.max(maxOps, 1 + dp(start + i));
            }
        }
        
        memo.set(start, maxOps);
        return maxOps;
    }
    
    return dp(0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n²)
空间复杂度O(n²)

其中 n 是字符串的长度。时间复杂度主要来自于预计算所有子串的相等性和动态规划的状态转移，空间复杂度主要用于存储 DP 数组和子串相等性矩阵。

相关题目