字符串的好分割数目

难度: Medium

给你一个字符串 s ，一个分割被称为「好分割」当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

请你返回 s 中好分割的数目。

示例 1：

输入：s = "aacaba"
输出：2
解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。

示例 2：

输入：s = "abcd"
输出：1
解释：好分割为将字符串分割成 ("ab", "cd") 。

示例 3：

输入：s = "aaaaa"
输出：4
解释：所有分割都是好分割。

示例 4：

输入：s = "acbadbaada"
输出：2

提示：

s 只包含小写英文字母。
1 <= s.length <= 10^5

Submission

运行时间: 70 ms

内存: 18.8 MB

class Solution:
    def numSplits(self, s: str) -> int:
        def check(s:str):
            dic1 = []
            memo = set()
            count = 0
            for word in s:
                if word not in memo:
                    count += 1
                    memo.add(word)
                dic1.append(count)
            return dic1


        nums1 = check(s)
        nums2 = check(s[::-1])[::-1]
        ans = 0
        n = len(s)
        for i in range(n-1):
            if nums1[i] == nums2[i + 1]:
                ans += 1
        return ans

Explain

这个题解采用了前缀和和后缀和的思路来计算字符串中不同字符的数量。首先，定义一个辅助函数 check，它会遍历输入字符串并使用一个集合来追踪遇到的不同字符，并将当前不同字符的计数存储在一个列表中。函数返回这个列表。对于原始字符串 s，我们计算一个前缀和 nums1，它记录了从字符串开始到当前位置的不同字符数量。对于翻转后的字符串 s[::-1]，我们同样计算一个类似的列表 nums2，然后将其反转，使之变成后缀和。最后，通过遍历这两个列表直到倒数第二个字符，并比较前缀和和对应的后缀和是否相等，来确定是否是好分割。若相等，则增加答案计数器 ans。这种方法有效地利用了前缀和和后缀和的对比来避免重复计算，从而优化了性能。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def numSplits(self, s: str) -> int:
        def check(s:str):
            dic1 = []  # 存储从左到右或从右到左的不同字符的数量
            memo = set()  # 记录已经遇到的字符
            count = 0  # 不同字符的计数
            for word in s:
                if word not in memo:
                    count += 1  # 发现新字符，计数增加
                    memo.add(word)  # 添加到集合中
                dic1.append(count)  # 记录到当前位置的不同字符数量
            return dic1

        nums1 = check(s)  # 原字符串的前缀和
        nums2 = check(s[::-1])[::-1]  # 翻转字符串的后缀和
        ans = 0  # 初始化好分割计数器
        n = len(s)
        for i in range(n-1):
            if nums1[i] == nums2[i + 1]:
                ans += 1  # 如果前缀和等于后缀和，则是好分割
        return ans

Explore

题解中的`check`函数使用Python的`set`来记录字符，Python的字符串是基于Unicode编码的。这意味着无论输入字符串中的字符属于ASCII还是任何其他Unicode字符，`set`都能正确地处理和记录这些字符。因此，这种方法对于包含非常规字符的字符串同样是准确的，可以有效地处理多语言文本或特殊符号。

在这个题解中，比较前缀和和后缀和是否相等的过程是在长度相同的位置进行的。`nums1`列表记录了从左到右每个位置的不同字符数量，而`nums2`列表则记录了从右到左每个位置的不同字符数量，并已经反转以匹配前缀位置。因此，每次比较都是在相同长度的切片上进行，不会出现由于字符串长度不同而影响判断的情况。

`set`在Python中是一个高效的数据结构，特别适用于需要快速检索、添加和删除元素的场景。在这种情况下，我们需要检查一个字符是否已经被记录过，`set`提供了平均时间复杂度为O(1)的成员检查和插入操作。使用`dict`可能也可以实现同样的功能，但在这种情况下使用`set`更为直接和高效，因为我们只关心字符的存在性，不关心字符的数量或其他属性。

这种做法直接关联到数组的边界条件。在寻找好分割的过程中，如果遍历到字符串的最后一个字符，则后缀部分将为空，而前缀部分将是整个字符串。这种情况下，前缀和后缀无法形成有效的分割（因为至少需要有字符在后缀中）。因此，遍历到倒数第二个字符是为了确保后缀至少包含一个字符，从而满足分割的基本要求。