题目描述
思路解析
一句话答案：LeetCode 1525 字符串的好分割数目：一遍扫描枚举切点，增量维护左段集合与右段计数表，省去每个切点重数两段；两边不同字符数相等即好分割。时间 O(n)、空间 O(1)。
好分割到底要左右两段满足什么
给一个只含小写字母的字符串 s，在某处切成非空的左段 p 和右段 q。若 p 的不同字符种数恰好等于 q 的不同字符种数，这个切点就是「好分割」，返回好分割的总数。以 s =「aacaba」为例：「aac」和「aba」左右各 2 种，是好分割；「aaca」和「ba」也各 2 种；其余切点两边不等。答案是 2。
每个切点都把两段重新数，慢在哪
长度 n 的串有 n-1 个可切位置。对每个切点把左右两段各数一遍不同字符，单个切点要扫近 n 个字符，合起来是 O(n²)（大 O 记号，描述数据变大时操作数怎么涨）。相邻切点其实只差一个字符的交接，这么数大半是重复劳动。
左段只增右段只减，两边不同数怎么一次扫出来
相邻切点只挪一个字符，与其每次重数，不如让两段的不同数跟着分界线增量维护（顺手改一下、不推倒重来）。左段用集合 vis（自动去重，同一字符放几次只占一格）装见过的字符，大小就是左段不同数，只增不减。右段用计数表 cnt（哈希表，记每个字符在右段还剩几个），先存整串计数当起点，每交接走一个字符就把它那格减一，某格减到 0 就删这一行，cnt 的行数就是右段不同数。
右段不同数为什么只在某个字符清零时才降
最容易数错的是右段不同数何时降。右段计数减一，并不等于右段不同数减一：a 有 4 个，交接走一个后它从 4 减到 3，可 a 后面还有，这行不删、右段不同数不动。只有某字符减到 0、在右段没了，才删那行、不同数降一格。左段同理，集合只在遇到全新字符时才涨。每滑一步比 vis 大小和 cnt 行数，相等就攒一个好分割。
拿 aacaba 把每个切点的两边不同数逐个走一遍
起点：cnt 装整串，a 4 个、c 和 b 各 1 个共 3 种，vis 空 0 种。分界线从左往右挪，逐个切点算。交接第 1 个 a：vis 成 {a} 左 1 种，a 从 4 减到 3 没清零、右仍 3 种，1 ≠ 3。交接第 2 个 a：左仍 1 种，a 从 3 减到 2、右仍 3 种，1 ≠ 3。交接 c：vis 成 {a, c} 左 2 种，c 从 1 减到 0 清零删行、右剩 a、b 共 2 种，2 = 2 记 1。交接第 3 个 a：左仍 2 种，a 从 2 减到 1 没清零、右仍 2 种，2 = 2 记 2。交接 b：vis 成 {a, c, b} 左 3 种，b 从 1 减到 0 清零删行、右剩 1 种，3 ≠ 1。交接末个 a：a 从 1 减到 0 清零删行、右 0 种，3 ≠ 0。全程只有第三、第四个切点相等，答案 2，和题面对上。
扫到末尾右段空成 0 种，为什么不会被误记成好分割
最后交接完整串那步：左段整串 3 种、右段掏空 0 种，不相等，不会误算。它本就不是合法切点——右段必须非空，空右段 0 种永远配不上至少 1 种的非空左段，不用特判，扫描自己就跳过。复杂度上，建计数表与滑分界线各扫一遍，每字符只做常数功，合计 O(n)；vis 和 cnt 各最多 26 项，与串长无关，空间 O(1)。另一个边界：全相同字符的串除末格外每个切点左右都 1 种、都相等，全是好分割。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句话:左段的集合往大长,右段的计数往小缩,两边不同数一相等就是一个好分割。下面每一帧都在套这个思路。
准备 · 右段从整串开始：开滑之前先看舞台。上面这排是字符串 "aacaba" 的每个字符。右边面板是右段计数 cnt,现在分界线还在最左边,左段是空的、右段就是整串,所以 cnt 里记着整串的字符:a 有 4 个、c 有 1 个、b 有 1 个,一共 3 种不同字符,这就是右段当前的不同数。左段集合 vis 现在空空如也,不同数是 0。
准备 · 分界线怎么滑：说清楚滑动规则。分界线会从最左边一格一格往右挪。每当它滑过一个字符,这个字符就从右段交接到左段:一方面把它加进左段集合 vis,另一方面把右段计数 cnt 里对应的那一格减一。减到 0 就代表这个字符在右段彻底没了,要把那一行删掉。挪一步、比一次两边的不同数,相等就攒一个好分割。下面正式开滑。
切点 0 · 左段并入 "a"：分界线滑到下标 0,把字符 "a" 交接给左段。左段集合 vis 之前没有 "a",这一加就多了一种字符,左段不同数变成 1,现在左段是 {a}。
切点 0 · 右段 "a" 减一：同一个字符 "a" 从右段走掉了一个,所以把右段计数里它那一格减一,从 4 变成 3。还没减到 0,"a" 在右段后面还会出现,所以这一行保留,右段不同数仍是 3。右段不同数只在某字符彻底清零时才会降。
切点 0 · 比一比：左段是 "a",右段是 "acaba"。左段不同数 1,右段不同数 3。两边不相等,这个切点不算好分割,ans 保持 0,继续往右滑。
切点 1 · 左段并入 "a"：分界线滑到下标 1,把字符 "a" 交接给左段。左段集合 vis 早就有 "a" 了,再加也是同一个,所以集合不变,左段不同数还是 1,仍是 {a}。这一步告诉你,左段不同数只在遇到全新字符时才会涨。
切点 1 · 右段 "a" 减一：同一个字符 "a" 从右段走掉了一个,所以把右段计数里它那一格减一,从 3 变成 2。还没减到 0,"a" 在右段后面还会出现,所以这一行保留,右段不同数仍是 3。右段不同数只在某字符彻底清零时才会降。
切点 1 · 比一比：左段是 "aa",右段是 "caba"。左段不同数 1,右段不同数 3。两边不相等,这个切点不算好分割,ans 保持 0,继续往右滑。
切点 2 · 左段并入 "c"：分界线滑到下标 2,把字符 "c" 交接给左段。左段集合 vis 之前没有 "c",这一加就多了一种字符,左段不同数变成 2,现在左段是 {a, c}。
切点 2 · 右段 "c" 减一：同一个字符 "c" 从右段走掉了一个,所以把右段计数里它那一格减一,从 1 变成 0。减到 0 了,说明 "c" 在右段一个都不剩,要把这一行从表里删掉。表里少一行,右段不同数就降到 2。
切点 2 · 比一比：左段是 "aac",右段是 "aba"。左段不同数 2,右段不同数 2。两边正好相等,这个切点是好分割,ans 加一变成 1。屏幕上绿色高亮的就是这次切出的左段。
切点 3 · 左段并入 "a"：分界线滑到下标 3,把字符 "a" 交接给左段。左段集合 vis 早就有 "a" 了,再加也是同一个,所以集合不变,左段不同数还是 2,仍是 {a, c}。这一步告诉你,左段不同数只在遇到全新字符时才会涨。
切点 3 · 右段 "a" 减一：同一个字符 "a" 从右段走掉了一个,所以把右段计数里它那一格减一,从 2 变成 1。还没减到 0,"a" 在右段后面还会出现,所以这一行保留,右段不同数仍是 2。右段不同数只在某字符彻底清零时才会降。
切点 3 · 比一比：左段是 "aaca",右段是 "ba"。左段不同数 2,右段不同数 2。两边正好相等,这个切点是好分割,ans 加一变成 2。屏幕上绿色高亮的就是这次切出的左段。
切点 4 · 左段并入 "b"：分界线滑到下标 4,把字符 "b" 交接给左段。左段集合 vis 之前没有 "b",这一加就多了一种字符,左段不同数变成 3,现在左段是 {a, c, b}。
切点 4 · 右段 "b" 减一：同一个字符 "b" 从右段走掉了一个,所以把右段计数里它那一格减一,从 1 变成 0。减到 0 了,说明 "b" 在右段一个都不剩,要把这一行从表里删掉。表里少一行,右段不同数就降到 1。
切点 4 · 比一比：左段是 "aacab",右段是 "a"。左段不同数 3,右段不同数 1。两边不相等,这个切点不算好分割,ans 保持 2,继续往右滑。
切点 5 · 左段并入 "a"：分界线滑到下标 5,把字符 "a" 交接给左段。左段集合 vis 早就有 "a" 了,再加也是同一个,所以集合不变,左段不同数还是 3,仍是 {a, c, b}。这一步告诉你,左段不同数只在遇到全新字符时才会涨。
切点 5 · 右段 "a" 减一：同一个字符 "a" 从右段走掉了一个,所以把右段计数里它那一格减一,从 1 变成 0。减到 0 了,说明 "a" 在右段一个都不剩,要把这一行从表里删掉。表里少一行,右段不同数就降到 0。
切点 5 · 比一比：左段是 "aacaba",右段是 "空"。左段不同数 3,右段不同数 0。分界线已经滑到末尾,右段是空的、不同数 0,这不是一个真正的切点,自然不相等,ans 保持 2。这一帧顺便说明:右段为空时永远配不上非空的左段,所以最后这一格不会误判成好分割。
完成 · 答案 2：分界线滑到了最右边,右段计数全部清空,所有字符都交接给了左段。回放一下:整条路上只有两个切点让左右两段的不同数相等,分别是 "aac | aba" 和 "aaca | ba",这两个切点左右两段都各有 2 种不同字符。所以好分割一共 2 个。全程只把字符串扫了一遍,每一步只做并入、减一、比较三个常数操作。
边界先想清:全相同字符时除末尾外全是好分割、严格递增的不同字符往往凑不出相等、两个不同字符切中间正好平分。
面试重点:左段只增用集合、右段只减用计数表、它是枚举分界点两侧各维护状态的前后缀套路。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def numSplits(self, s: str) -> int: cnt = Counter(s) vis = set() ans = 0 for c in s: vis.add(c) cnt[c] -= 1 if cnt[c] == 0: cnt.pop(c) ans += len(vis) == len(cnt) return ans复杂度
- 时间：O(n)，n 是字符串长度。先扫一遍建计数,再扫一遍滑分界线,每个字符做的事是集合加一次、计数减一次、比一次大小,都是常数时间,合计 O(n)
- 空间：O(1)，左段集合 vis 和右段计数 cnt 装的都是小写字母,最多各 26 项,是与 n 无关的常数,所以额外空间峰值是 O(1)(也可记作 O(字符集大小))
易错点
面试追问把动画讲成自己的话
追问为什么左段用集合、右段用计数表,两边用的结构不一样?
追问能不能不维护右段,改成预先算好每个位置右边的不同字符数?
追问这道题属于哪一类套路,以后遇到类似的怎么认?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
乘积为正数的最长子数组长度
LeetCode 1567 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题