字符串的好分割数目

记牢一句话:左段的集合往大长,右段的计数往小缩,两边不同数一相等就是一个好分割。下面每一帧都在套这个思路。

准备 · 右段从整串开始：开滑之前先看舞台。上面这排是字符串 "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 个。全程只把字符串扫了一遍,每一步只做并入、减一、比较三个常数操作。

边界先想清:全相同字符时除末尾外全是好分割、严格递增的不同字符往往凑不出相等、两个不同字符切中间正好平分。

面试重点:左段只增用集合、右段只减用计数表、它是枚举分界点两侧各维护状态的前后缀套路。