M2405.子字符串的最优划分

greedy, bit manipulation, https://leetcode.cn/problems/optimal-partition-of-string/

给你一个字符串 s ，请你将该字符串划分成一个或多个 子字符串 ，并满足每个子字符串中的字符都是 唯一 的。也就是说，在单个子字符串中，字母的出现次数都不超过 一次 。

满足题目要求的情况下，返回 最少 需要划分多少个子字符串。

注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。

示例 1：

输入：s = "abacaba"
输出：4
解释：
两种可行的划分方法分别是 ("a","ba","cab","a") 和 ("ab","a","ca","ba") 。
可以证明最少需要划分 4 个子字符串。

示例 2：

输入：s = "ssssss"
输出：6
解释：
只存在一种可行的划分方法 ("s","s","s","s","s","s") 。

提示：

• 1 <= s.length <= 10^5
• s 仅由小写英文字母组成

这是一个典型的贪心算法问题。

解题思路

为了使划分出的子字符串数量最少，我们应该让每一个子字符串尽可能地长。

1. 贪心策略：从左到右遍历字符串，将字符逐个加入当前的子字符串中。
2. 冲突检测：如果当前字符已经存在于当前的子字符串中，说明当前子字符串必须在此处截止。
3. 更新状态：一旦发生冲突，我们将划分计数加 1，然后开始一个新的子字符串，这个新字符串的第一个字符就是当前产生冲突的字符。
4. 优化：由于字符集仅由小写英文字母组成（共 26 个），我们可以使用一个哈希集合（Set）来记录当前子字符串中出现的字符。或者为了更高的效率，使用位掩码（Bitmask）来替代集合。

代码实现（使用位掩码优化）

class Solution:
    def partitionString(self, s: str) -> int:
        # ans 初始化为 1，因为至少会有一个子字符串
        ans = 1
        # seen 用于记录当前子字符串中出现的字符，使用位运算模拟集合
        seen = 0
        
        for char in s:
            # 计算当前字符对应的位偏移量 (0-25)
            val = ord(char) - ord('a')
            
            # 如果该位已经是 1，说明字符重复了
            if seen & (1 << val):
                # 开启一个新的子字符串
                ans += 1
                # 重置 seen，仅包含当前这一个新字符
                seen = (1 << val)
            else:
                # 否则，将当前字符加入 seen 中
                seen |= (1 << val)
                
        return ans

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 s 的长度。我们只需要遍历一遍字符串。
• 空间复杂度：$O(1)$。虽然我们使用了 seen 变量，但它本质上是一个整数（位掩码），且字符集大小固定为 26。如果使用哈希集合，空间复杂度也是 $O(1)$，因为集合大小最大不会超过 26。

示例执行过程 (s = "abacaba")

1. 遇到 'a': seen = 00...01 (a), ans = 1
2. 遇到 'b': seen = 00...11 (ab), ans = 1
3. 遇到 'a': 冲突！ans = 2, seen = 00...01 (a)
4. 遇到 'c': seen = 00...101 (ac), ans = 2
5. 遇到 'a': 冲突！ans = 3, seen = 00...01 (a)
6. 遇到 'b': seen = 00...11 (ab), ans = 3
7. 遇到 'a': 冲突！ans = 4, seen = 00...01 (a)
8. 结束，返回 4。