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

难度: Hard

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

你需要执行以下分割操作，直到字符串 s 变为空：

选择 s 的最长前缀，该前缀最多包含 k 个不同字符。
删除这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。

执行操作之前，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。

在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的最大分割数量。

示例 1：

输入：s = "accca", k = 2
输出：3
解释：在此示例中，为了最大化得到的分割数量，可以将 s[2] 改为 'b'。
s 变为 "acbca"。
按照以下方式执行操作，直到 s 变为空：
- 选择最长且至多包含 2 个不同字符的前缀，"acbca"。
- 删除该前缀，s 变为 "bca"。现在分割数量为 1。
- 选择最长且至多包含 2 个不同字符的前缀，"bca"。
- 删除该前缀，s 变为 "a"。现在分割数量为 2。
- 选择最长且至多包含 2 个不同字符的前缀，"a"。
- 删除该前缀，s 变为空。现在分割数量为 3。
因此，答案是 3。
可以证明，分割数量不可能超过 3。

示例 2：

输入：s = "aabaab", k = 3
输出：1
解释：在此示例中，为了最大化得到的分割数量，可以保持 s 不变。
按照以下方式执行操作，直到 s 变为空： 
- 选择最长且至多包含 3 个不同字符的前缀，"aabaab"。
- 删除该前缀，s 变为空。现在分割数量为 1。
因此，答案是 1。
可以证明，分割数量不可能超过 1。

示例 3：

输入：s = "xxyz", k = 1
输出：4
解释：在此示例中，为了最大化得到的分割数量，可以将 s[1] 改为 'a'。
s 变为 "xayz"。
按照以下方式执行操作，直到 s 变为空：
- 选择最长且至多包含 1 个不同字符的前缀，"xayz"。
- 删除该前缀，s 变为 "ayz"。现在分割数量为 1。
- 选择最长且至多包含 1 个不同字符的前缀，"ayz"。
- 删除该前缀，s 变为 "yz"，现在分割数量为 2。
- 选择最长且至多包含 1 个不同字符的前缀，"yz"。
- 删除该前缀，s 变为 "z"。现在分割数量为 3。
- 选择最且至多包含 1 个不同字符的前缀，"z"。
- 删除该前缀，s 变为空。现在分割数量为 4。
因此，答案是 4。
可以证明，分割数量不可能超过 4。

提示：

1 <= s.length <= 10⁴
s 只包含小写英文字母。
1 <= k <= 26

Submission

运行时间: 61 ms

内存: 17.3 MB

class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        if k == 26:
            return 1
        seg, mask, size = 1, 0, 0

        def update(i: int) -> None:
            nonlocal seg, mask, size
            bit = 1 << (ord(s[i]) - ord("a"))
            if mask & bit:
                return

            size += 1
            if size > k:
                seg += 1
                mask = bit
                size = 1
            else:
                mask |= bit

        n = len(s)
        suf = [None] * n + [(0, 0)]
        for i in range(n - 1, -1, -1):
            update(i)
            suf[i] = (seg, mask)
        ans = seg
        seg, mask, size = 1, 0, 0
        for i in range(n):
            suf_seg, suf_mask = suf[i + 1]
            res = seg + suf_seg
            union_size = (mask | suf_mask).bit_count()
            if union_size < k:
                res -= 1
            elif union_size < 26 and size == k and suf_mask.bit_count() == k:
                res += 1
            ans = max(ans, res)
            update(i)
        return ans

Explain

这道题的核心是通过一次或不通过修改任何字符，来最大化字符串s的分割次数。首先，如果k等于26（字母表的长度），可以一次性删除整个字符串，所以答案为1。题解使用两个遍历过程：首先，从右向左遍历字符串，记录每个位置为起始点的段数和所包含的字符（使用位掩码表示）。然后，再从左向右遍历字符串，并结合已存储的后缀信息来决定修改字符的位置，以最大化分割数。第二遍遍历尝试通过字符替换来优化可能的分割方式，最终更新并返回最大分割数。

时间复杂度: O(n)

空间复杂度: O(n)

# This class contains the method to determine the maximum number of partitions.

 class Solution:
     def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
         if k == 26:
             return 1 # If k is 26, we can delete the whole string at once.

         seg, mask, size = 1, 0, 0

         # Helper function to update the mask and segment count.
         def update(i: int) -> None:
             nonlocal seg, mask, size
             bit = 1 << (ord(s[i]) - ord('a')) # Compute the bit mask for current character.
             if mask & bit:
                 return # Character already counted.

             size += 1 # New character found, increase size.
             if size > k:
                 seg += 1 # Start a new segment.
                 mask = bit
                 size = 1
             else:
                 mask |= bit # Include this character in the current mask.

         n = len(s)
         suf = [None] * n + [(0, 0)] # Initialize suffix array.
         for i in range(n - 1, -1, -1):
             update(i)
             suf[i] = (seg, mask) # Store segment count and mask for this suffix.

         ans = seg
         seg, mask, size = 1, 0, 0 # Reset for the second pass.
         for i in range(n):
             suf_seg, suf_mask = suf[i + 1] # Get suffix info.
             res = seg + suf_seg # Combine segments.
             union_size = (mask | suf_mask).bit_count() # Count unique characters in combined segment.
             if union_size < k:
                 res -= 1 # If under k characters, we can combine into fewer segments.
             elif union_size < 26 and size == k and suf_mask.bit_count() == k:
                 res += 1 # Check if we can optimize by adjusting characters.
             ans = max(ans, res) # Update the maximum answer.
             update(i) # Update mask and segment count for this index.
         return ans # Return the maximum number of partitions.

Explore

题解中通过两次遍历和位掩码来尝试优化分割，确保最多修改一处字符的策略主要依赖于第二次遍历时评估合并段落的可能性。通过计算当前段落和后缀段落的字符集的并集大小来决定是否可以通过修改一个字符来减少分割数。如果并集大小小于k且当前段和后缀段的字符集大小都已达到k，通过替换一个字符可能实现两个段合并。这种策略尝试在不超过修改一次的情况下，通过智能合并来达到最大分割数。

位掩码是一种通过位运算来跟踪和操作数据的方法。在这个题解中，每个字符被映射到一个位上，例如'a'对应第0位，'b'对应第1位，依此类推。这样做的优势在于，位掩码可以高效地进行字符集的并、交和差运算，例如检查特定字符是否已存在（通过AND运算），添加新字符（通过OR运算），并且计算掩码中位为1的个数（即字符集大小）也非常高效。这种方法在处理字符集和分段操作时提供了一种紧凑且速度快的解决方案。

题解中的第一次遍历从右向左的目的是为了建立后缀信息，即从每个位置到字符串末尾的段数和字符集。这样做可以在第二次遍历时快速获取任何位置右侧的段信息。第二次遍历从左向右，则是用来结合这些后缀信息来尝试优化分割策略，例如通过合并段落来减少分割数。这两次遍历结合起来，使得算法能在遍历过程中动态调整策略，从而实现最优分割。

在`update`函数中，当遇到已经在当前段的字符掩码中的字符时，该字符不会引起段数的增加，也不会改变掩码的状态，因为该字符已被当前段包含。这种处理确保了每个段中的字符集合是独立且不重复的，从而正确地记录和更新段的数量。这也意味着函数只在发现新字符或必须开始新段时才更新段数和掩码，从而精确地控制分割点。