字符串的好分割数目 图解题解

好分割到底要左右两段满足什么

给一个只含小写字母的字符串 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 种、都相等，全是好分割。

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numSplits(string s) {
        unordered_map<char, int> cnt;
        for (char& c : s) {
            ++cnt[c];
        }
        unordered_set<char> vis;
        int ans = 0;
        for (char& c : s) {
            vis.insert(c);
            if (--cnt[c] == 0) {
                cnt.erase(c);
            }
            ans += vis.size() == cnt.size();
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int numSplits(String s) {
        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : s.toCharArray()) {
            cnt.merge(c, 1, Integer::sum);
        }
        Set<Character> vis = new HashSet<>();
        int ans = 0;
        for (char c : s.toCharArray()) {
            vis.add(c);
            if (cnt.merge(c, -1, Integer::sum) == 0) {
                cnt.remove(c);
            }
            if (vis.size() == cnt.size()) {
                ++ans;
            }
        }
        return ans;
    }
}