LeetCode 题解工作台
对字母串可执行的最大删除数
给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以： 删除 整个字符串 s ，或者 对于满足 1 的任意 i ，如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ，删除 前 i 个字母。 例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 ，表示删除 所有字符所需的最大操作数，那么答案就是 。 函数 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个仅由小写英文字母组成的字符串 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仅由小写英文字母组成
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示删除 所有字符所需的最大操作数，那么答案就是 。
函数 的计算过程如下：
- 如果 ，那么 ，直接返回。
- 否则，我们枚举字符串的长度 ，其中 ，如果 ，那么我们可以删除 ，此时 。我们需要枚举所有的 ，求 的最大值即可。
这里我们需要快速判断 与 是否相等，我们可以预处理出字符串 的所有最长公共前缀，即 表示 与 的最长公共前缀的长度。这样我们就可以快速判断 与 是否相等，即 。
为了避免重复计算，我们可以使用记忆化搜索，用一个数组 记录函数 的值。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
class Solution:
def deleteString(self, s: str) -> int:
@cache
def dfs(i: int) -> int:
if i == n:
return 0
ans = 1
for j in range(1, (n - i) // 2 + 1):
if s[i : i + j] == s[i + j : i + j + j]:
ans = max(ans, 1 + dfs(i + j))
return ans
n = len(s)
return dfs(0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) in the worst case without optimization, but rolling hash reduces substring comparisons to O(1), keeping the overall solution within acceptable bounds. Space complexity is O(n) for the dp array and hash arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks if dynamic programming is suitable for prefix-based deletions.
- question_mark
Mentions performance concerns for strings up to 4000 characters.
- question_mark
Checks understanding of rolling hash for substring comparison.
常见陷阱
外企场景- error
Forgetting to compare only valid k-length prefixes within bounds.
- error
Ignoring edge cases where the string has repeated single characters.
- error
Recomputing substrings without hashing, causing timeouts.
进阶变体
外企场景- arrow_right_alt
Maximum deletions on a string allowing overlapping prefix matches.
- arrow_right_alt
Find maximum deletions where substrings may be reversed before comparison.
- arrow_right_alt
Calculate maximum deletions with additional constraint on minimum prefix length.