题目描述

给你一个字符串 s，一个分割被称为完美的，当它满足：将 s 分割成 2 个字符串 p 和 q，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

请你返回 s 中完美分割的数目。

样例

输入：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 个不同的字符。

输入：s = "abcd"
输出：1
解释：完美分割为将字符串分割成 ("ab", "cd") 。

输入：s = "aaaaa"
输出：4
解释：所有分割都是完美分割。

输入：s = "acbadbaada"
输出：2

限制

• s 只包含小写英文字母。
• 1 <= s.length <= 10^5

算法

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

1. 我们首先统计出来每个字母的出现次数，以及不同字母的种类数。
2. 定义 $L(i)$ 和 $R(i)$，分别表示前 $i$ 个字符的种类数和除去前 $i$ 个字符以外的不同字母的种类数。
3. $i$ 从 0 开始循环到 $n - 1$，每次我们都可以快速的由 $L(i - 1)$ 计算出 $L(i)$，以及从 $R(i - 1)$ 计算出 $R(i)$。

时间复杂度

• 每个位置仅需要常数的时间转移，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    void add(vector<int> &a, int &cnt, int c) {
        if (a[c] == 0) 
            cnt++;
        a[c]++;
    }

    void remove(vector<int> &a, int &cnt, int c) {
        a[c]--;
        if (a[c] == 0) 
            cnt--;
    }

public:
    int numSplits(string s) {
        int cntL = 0, cntR = 0;
        vector<int> L(26, 0), R(26, 0);

        for (char ch : s) {
            int c = ch - 'a';
            add(R, cntR, c);
        }

        const int n = s.size();
        int ans = 0;

        for (int i = 0; i < n - 1; i++) {
            int c = s[i] - 'a';
            add(L, cntL, c);
            remove(R, cntR, c);
            if (cntL == cntR)
                ans++;
        }

        return ans;
    }
};