3003. 执行操作后的最大分割数量

在力扣 App 中打开

调试中...

题目描述

题解

提交记录

代码

测试用例

测试结果

3003. 执行操作后的最大分割数量

困难

相关企业

提示

给你一个下标从 0 开始的字符串 s 和一个整数 k。

你需要执行以下分割操作，直到字符串 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 <= 10⁴
s 只包含小写英文字母。
1 <= k <= 26

通过次数

1.8K

提交次数

6.7K

通过率

26.4%

相关企业

提示 1

For each position, try to brute-force the replacements.

提示 2

To speed up the brute-force solution, we can precompute the following (without changing any index) using prefix sums and binary search:

pref[i]: The number of resulting partitions from the operations by performing the operations on s[0:i].
suff[i]: The number of resulting partitions from the operations by performing the operations on s[i:n - 1], where n == s.length.
partition_start[i]: The start index of the partition containing the i^th index after performing the operations.

提示 3

Now, for a position i, we can try all possible 25 replacements:
For a replacement, using prefix sums and binary search, we need to find the rightmost index, r, such that the number of distinct characters in the range [partition_start[i], r] is at most k.
There are 2 cases:

r >= i: the number of resulting partitions in this case is 1 + pref[partition_start[i] - 1] + suff[r + 1].
Otherwise, we need to find the rightmost index r₂ such that the number of distinct characters in the range [r:r₂] is at most k. The answer in this case is 2 + pref[partition_start[i] - 1] + suff[r₂ + 1]