---

1525. 字符串的好分割数目

• 标签：位运算、哈希表、字符串、动态规划
• 难度：中等

题目链接

• 1525. 字符串的好分割数目 - 力扣

题目大意

描述：给定一个字符串 $s$，将其分割成两个非空子字符串 $left$ 和 $right$。

要求：返回好分割的数目。好分割指 $left$ 中不同字符数等于 $right$ 中不同字符数。

说明：

• $2 \le s.length \le 10^5$。
• $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") 。

解题思路

思路 1：前缀统计 + 后缀统计

1. 核心思想

先统计整个字符串中每个字符的出现次数（作为 $right$ 部分的初始统计），然后从左到右遍历分割点，将当前字符从 $right$ 移到 $left$，比较两边的不同字符数。

2. 具体步骤

第 1 步：统计 $right$ 部分（整个字符串）的字符频率 $right\_freq$。计算 $right$ 的不同字符数 $right\_unique$。

第 2 步：初始化 $left\_freq$ 全 $0$，$left\_unique = 0$。

第 3 步：遍历 $i = 0 \to n-2$（分割点）：

• 将 $s[i]$ 从 $right$ 移到 $left$：
  • 如果 $right\_freq[s[i]] == 1$：$right\_unique -= 1$。
  • $right\_freq[s[i]] -= 1$。
  • 如果 $left\_freq[s[i]] == 0$：$left\_unique += 1$。
  • $left\_freq[s[i]] += 1$。
• 如果 $left\_unique == right\_unique$：$ans += 1$。

第 4 步：返回 $ans$。

3. 举例说明

以 $s = "aacaba"$ 为例：

• 初始：$right$ 各字符频率，$right\_unique = 3$（a, c, b）。

$i=0$：$s[0]='a'$。

• $right$ 中 a 还有 $2$ 个，$right\_unique$ 不变。
• $left$：$a$，$left\_unique=1 \neq 3$。

$i=1$：$s[1]='a'$。

• $right$ 中 a 还有 $1$ 个，$right\_unique$ 不变。
• $left$：$aa$，$left\_unique=1 \neq 3$。

$i=2$：$s[2]='c'$。

• $right$ 中 c 还有 $0$ 个，$right\_unique=2$。
• $left$：$aac$，$left\_unique=2$。
• $2 == 2$，$ans=1$。

$i=3$：$s[3]='a'$。

• $right$ 中 a 还有 $0$ 个，$right\_unique=1$。
• $left$：$aaca$，$left\_unique=2 \neq 1$。

$i=4$：$s[4]='b'$。

• $right$ 中 b 还有 $0$ 个，$right\_unique=1$。（等等不对，b 已经没有了...）

嗯让我重新算。

实际上 $s = "aacaba"$，$n=6$。

初始 $right$ 频率：a:4, c:1, b:1。$right\_unique=3$。

$i=0$：移 'a' 到 left。

• right: a:3, $right\_unique$ 仍为 3。
• left: a:1, $left\_unique=1$。$1 \neq 3$。

$i=1$：移 'a'。

• right: a:2, $right\_unique$ 仍为 3。
• left: a:2, $left\_unique=1$。$1 \neq 3$。

$i=2$：移 'c'。

• right: c:0, $right\_unique=2$（c 没了）。
• left: a:2, c:1, $left\_unique=2$。$2 == 2$，$ans=1$。

$i=3$：移 'a'。

• right: a:1, $right\_unique$ 仍为 2。
• left: a:3, c:1, $left\_unique=2$。$2 == 2$，$ans=2$。

$i=4$：移 'b'。

• right: b:0, $right\_unique=1$（b 没了，只剩 a）。
• left: a:3, c:1, b:1, $left\_unique=3$。$3 \neq 1$。

$ans=2$。

检查结果：分割点 $i=2$（"aac" | "aba"），$i=3$（"aaca" | "ba"）。

验证："aac" 有 {a,c}，"aba" 有 {a,b}，都是 $2$ 种。✓
"aaca" 有 {a,c}，"ba" 有 {b,a}，都是 $2$ 种。✓

思路 1：代码

class Solution:
    def numSplits(self, s: str) -> int:
        right_freq = [0] * 26
        for ch in s:
            right_freq[ord(ch) - 97] += 1
        right_unique = sum(1 for c in right_freq if c > 0)

        left_freq = [0] * 26
        left_unique = 0
        ans = 0

        for ch in s:
            # 将 ch 从 right 移到 left
            idx = ord(ch) - 97
            # 从 right 移除
            if right_freq[idx] == 1:
                right_unique -= 1
            right_freq[idx] -= 1
            # 加入 left
            if left_freq[idx] == 0:
                left_unique += 1
            left_freq[idx] += 1

            if left_unique == right_unique:
                ans += 1

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(26) = O(1)$。