LeetCode 题解工作台
执行操作后的最大分割数量
给定一个字符串 s 和一个整数 k 。 首先，你最多可以更改 s 中的 一处 下标对应字符为另一个小写英文字母。 之后，执行以下分割操作，直到 s 变为 空串 ： 选择 s 的最长 前缀 ，该前缀最多包含 k 个 不同 字符。 从 s 中 删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $\textit{dfs}(i, \textit{cur}, t)$ 表示当前处理到字符串 的下标 ，当前前缀中已经包含的字符集合为 ，并且还可以修改 次字符时，能够得到的最大分割数量。那么答案即为 $\textit{dfs}(0, 0, 1)$。 函数 $\textit{dfs}(i, \textit{cur}, t)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个字符串 s 和一个整数 k。
首先，你最多可以更改 s 中的 一处 下标对应字符为另一个小写英文字母。
之后，执行以下分割操作，直到 s 变为 空串：
- 选择
s的最长 前缀，该前缀最多包含k个 不同 字符。 - 从
s中 删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在s中保持原来的顺序。
返回一个整数，表示在 最多 改变一处下标对应字符的情况下，经过操作后得到的最大分割数。
示例 1：
输入：s = "accca", k = 2
输出：3
解释：
最好的方式是把 s[2] 变为除了 a 和 c 之外的东西，比如 b。然后它变成了 "acbca"。
然后我们执行以下操作：
- 最多包含 2 个不同字符的最长前缀是
"ac"，我们删除它然后s变为"bca"。 - 现在最多包含 2 个不同字符的最长前缀是
"bc"，所以我们删除它然后s变为"a"。 - 最后，我们删除
"a"并且s变成空串，所以该过程结束。
进行操作时，字符串被分成 3 个部分，所以答案是 3。
示例 2：
输入：s = "aabaab", k = 3
输出：1
解释：
一开始 s 包含 2 个不同的字符，所以无论我们改变哪个， 它最多包含 3 个不同字符，因此最多包含 3 个不同字符的最长前缀始终是所有字符，因此答案是 1。
示例 3：
输入：s = "xxyz", k = 1
输出：4
解释：
最好的方式是将 s[0] 或 s[1] 变为 s 中字符以外的东西，例如将 s[0] 变为 w。
然后 s 变为 "wxyz"，包含 4 个不同的字符，所以当 k 为 1，它将分为 4 个部分。
提示：
1 <= s.length <= 104s只包含小写英文字母。1 <= k <= 26
解题思路
方法一：记忆化搜索
我们设计一个函数 表示当前处理到字符串 的下标 ，当前前缀中已经包含的字符集合为 ，并且还可以修改 次字符时，能够得到的最大分割数量。那么答案即为 。
函数 的执行逻辑如下：
- 如果 ，说明已经处理完字符串 ，返回 1。
- 计算当前字符 对应的位掩码 ，并计算更新后的字符集合 。
- 如果 中的位数超过 ，说明当前前缀已经包含超过 个不同字符，我们需要进行一次分割，此时分割数量加 1，并递归调用 ；否则，继续递归调用 。
- 如果 ，说明我们还可以修改一次字符。我们尝试将当前字符 修改为任意一个小写字母（共 26 种选择），对于每个选择，计算更新后的字符集合 ，并根据是否超过 个不同字符，选择相应的递归调用方式，更新最大分割数量。
- 使用哈希表缓存已经计算过的状态，避免重复计算。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度，而 为字符集大小。
class Solution:
def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
@cache
def dfs(i: int, cur: int, t: int) -> int:
if i >= n:
return 1
v = 1 << (ord(s[i]) - ord("a"))
nxt = cur | v
if nxt.bit_count() > k:
ans = dfs(i + 1, v, t) + 1
else:
ans = dfs(i + 1, nxt, t)
if t:
for j in range(26):
nxt = cur | (1 << j)
if nxt.bit_count() > k:
ans = max(ans, dfs(i + 1, 1 << j, 0) + 1)
else:
ans = max(ans, dfs(i + 1, nxt, 0))
return ans
n = len(s)
return dfs(0, 0, 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of state transitions in dynamic programming.
- question_mark
Evaluate their approach to managing distinct characters using bit manipulation.
- question_mark
Assess their ability to brute-force replacements and handle various string configurations.
常见陷阱
外企场景- error
Overlooking the impact of character replacements on the distinct character count during partitioning.
- error
Failing to account for the optimal replacement at each index, resulting in fewer partitions.
- error
Mismanaging the dynamic programming states and transitions, leading to inefficient solutions.
进阶变体
外企场景- arrow_right_alt
Maximizing partitions with more than one allowed replacement.
- arrow_right_alt
Limiting the number of partitions instead of maximizing them.
- arrow_right_alt
Changing characters at multiple indices to optimize partitioning.