难度: Medium
给你一个字符串 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 <= 105s 仅由小写英文字母组成运行时间: 76 ms
内存: 0.0 MB
class Solution:
def partitionString(self, s: str) -> int:
helper = set()
count = 1
for c in s:
if c not in helper:
helper.add(c)
else:
count += 1
helper = set()
helper.add(c)
return count
该题解的方法是使用一个集合（set）来保持当前子字符串中的字符集，以保证所有字符都是唯一的。遍历输入字符串s中的每个字符，对于每个字符c，如果c不在集合中，则将c添加到集合中。如果c已存在于集合中，这意味着我们需要开始一个新的子字符串，因此增加计数器count，并重置集合，然后将当前字符c添加到新的空集合中。最后，返回计数器count的值，即所需的最少子字符串数量。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def partitionString(self, s: str) -> int:
helper = set() # 初始化用于存储子字符串中字符的集合
count = 1 # 初始化子字符串计数器，至少有一个子字符串
for c in s: # 遍历输入字符串的每个字符
if c not in helper: # 如果字符不在当前子字符串集合中
helper.add(c) # 添加字符到集合中
else: # 如果字符已存在于集合中，需要开始新的子字符串
count += 1 # 子字符串计数器加1
helper = set() # 重置集合
helper.add(c) # 将当前字符加入新的集合中
return count # 返回所需的最少子字符串数量
当遇到一个已存在于当前子字符串集合中的字符时，选择立即开始一个新的子字符串是为了确保所有子字符串中的字符都是唯一的，这是题目的要求。如果尝试将该字符放入下一个可能的子字符串，我们无法预知未来的字符序列，也无法确定在哪里开始新的子字符串以避免重复，因此最简单直接的方法是在字符重复出现的地方立即切分。这种方法保证了算法的简洁性和正确性。
该算法在处理大规模数据时的性能和内存使用主要取决于字符串长度和字符的多样性。由于集合（set）在最坏情况下存储的是所有不同的字符，而通常字符种类（如ASCII或Unicode字符）有限，集合的大小不会超过字符集的大小。因此，内存使用上通常不是问题。性能方面，算法的时间复杂度为O(n)，其中n是字符串长度，因为每个字符只被处理一次。虽然对于极大的n值（接近105或更大），算法的执行时间会增加，但通常这种线性时间复杂度是可接受的。
在所有字符都不重复的特定情况下，该算法的分割结果是最优的，因为整个字符串可以作为一个单独的子字符串而不需要任何进一步的分割。算法在遍历字符时，由于集合中没有重复，不会触发新子字符串的开始，因此只会保持单一的子字符串计数。这正是在此特定情况下最优解的表现。