LeetCode 题解工作台
从原字符串里进行删除操作的最多次数
给你一个长度为 n 的字符串 source ，一个字符串 pattern 且它是 source 的 子序列 ，和一个 有序 整数数组 targetIndices ，整数数组中的元素是 [0, n - 1] 中 互不相同 的数字。 定义一次 操作 为删除 source 中下标在 idx 的一个字符，且…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们定义 表示在 的前 个字符串，匹配 的前 个字符的最大删除次数。初始时 $f[0][0] = 0$，其余 $f[i][j] = -\infty$。 对于 ，我们有两种选择：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个长度为 n 的字符串 source ，一个字符串 pattern 且它是 source 的 子序列 ，和一个 有序 整数数组 targetIndices ，整数数组中的元素是 [0, n - 1] 中 互不相同 的数字。
定义一次 操作 为删除 source 中下标在 idx 的一个字符，且需要满足：
idx是targetIndices中的一个元素。- 删除字符后，
pattern仍然是source的一个 子序列 。
执行操作后 不会 改变字符在 source 中的下标位置。比方说，如果从 "acb" 中删除 'c' ，下标为 2 的字符仍然是 'b' 。
请你返回 最多 可以进行多少次删除操作。
子序列指的是在原字符串里删除若干个（也可以不删除）字符后，不改变顺序地连接剩余字符得到的字符串。
示例 1：
输入：source = "abbaa", pattern = "aba", targetIndices = [0,1,2]
输出：1
解释：
不能删除 source[0] ，但我们可以执行以下两个操作之一：
- 删除
source[1]，source变为"a_baa"。 - 删除
source[2]，source变为"ab_aa"。
示例 2：
输入：source = "bcda", pattern = "d", targetIndices = [0,3]
输出：2
解释：
进行两次操作，删除 source[0] 和 source[3] 。
示例 3：
输入：source = "dda", pattern = "dda", targetIndices = [0,1,2]
输出：0
解释：
不能在 source 中删除任何字符。
示例 4：
输入：source = "yeyeykyded", pattern = "yeyyd", targetIndices = [0,2,3,4]
输出：2
解释：
进行两次操作，删除 source[2] 和 source[3] 。
提示：
1 <= n == source.length <= 3 * 1031 <= pattern.length <= n1 <= targetIndices.length <= ntargetIndices是一个升序数组。- 输入保证
targetIndices包含的元素在[0, n - 1]中且互不相同。 source和pattern只包含小写英文字母。- 输入保证
pattern是source的一个子序列。
解题思路
方法一：动态规划
我们定义 表示在 的前 个字符串，匹配 的前 个字符的最大删除次数。初始时 ，其余 。
对于 ，我们有两种选择：
- 我们可以跳过 的第 个字符，此时 ；
- 如果 ，我们可以匹配 的第 个字符，此时 。
最终答案即为 。
时间复杂度 ，空间复杂度 。其中 和 分别是 和 的长度。
class Solution:
def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int:
m, n = len(source), len(pattern)
f = [[-inf] * (n + 1) for _ in range(m + 1)]
f[0][0] = 0
s = set(targetIndices)
for i, c in enumerate(source, 1):
for j in range(n + 1):
f[i][j] = f[i - 1][j] + int((i - 1) in s)
if j and c == pattern[j - 1]:
f[i][j] = max(f[i][j], f[i - 1][j - 1])
return f[m][n]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log m) where n is the source length and m is targetIndices length due to binary search combined with two-pointer scans. Space complexity is O(m) for storing removal indices in a hash set. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for solutions using subsequence validation with minimal repeated scanning.
- question_mark
Check if candidate handles edge cases where pattern characters overlap with removal indices.
- question_mark
Evaluate the efficiency of two-pointer combined with hash lookup versus naive iteration.
常见陷阱
外企场景- error
Assuming removal shifts subsequent indices, which is incorrect for this problem's definition.
- error
Not handling cases where multiple pattern characters exist at removable indices.
- error
Inefficient repeated scans without using hash sets or dynamic programming, leading to timeouts.
进阶变体
外企场景- arrow_right_alt
Compute the minimum number of removals to make pattern no longer a subsequence.
- arrow_right_alt
Given multiple patterns, find the maximum removals that preserve all as subsequences.
- arrow_right_alt
Allow repeated characters in pattern and adjust removal strategy accordingly.