算法

(线性扫描) $O(n)$

这里的好分割指的是左边不同的字母数目和右边不同的字母数目一样，我们可以先统计一下s中每个字母出现的次数，记做sum，然后记录s中有多少不同的字母，作为右边不同的字母数目，记做qCnt。

接下来从左到右遍历分割线，用left数目表示到当前位置为止每个字母出现的次数，然后记录下pCnt，也就是到当前位置出现过多少不同的字母。

由于每次遍历的时候右边都会少一个字母，所以qCnt应该是递减的。当前字母在左边出现的次数等于它在整个字符串中出现的次数，那么说明它这个字母只在左半部分出现过，所以要把右边出现的字母数量减掉1。

这样就同时维护了pCnt和qCnt，如果在遍历过程中二者相等的话，那么我们就可得到一种合法的分割方案，把答案增加1个即可。

C++ 代码

class Solution {
public:
    int numSplits(string s) {
        vector<int> left(26), sum(26);
        int pCnt = 0, qCnt = 0;
        for (char ch : s) {
            ++sum[ch - 'a'];
            if (sum[ch - 'a'] == 1) ++qCnt;
        }

        int ans = 0;
        for (char ch : s) {
            ++left[ch - 'a'];
            if (left[ch - 'a'] == 1) ++pCnt;
            if (left[ch - 'a'] == sum[ch - 'a']) --qCnt;
            if (pCnt == qCnt) ++ans;
        }

        return ans;
    }
};