题目描述

给你一个二进制串 s（一个只包含 0 和 1 的字符串），我们可以将 s 分割成 3 个 非空 字符串 s1，s2，s3（s1 + s2 + s3 = s）。

请你返回分割 s的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。

由于答案可能很大，请将它对 10^9 + 7 取余后返回。

样例

输入：s = "10101"
输出：4
解释：总共有 4 种方法将 s 分割成含有 '1' 数目相同的三个子字符串。
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"

输入：s = "1001"
输出：0

输入：s = "0000"
输出：3
解释：总共有 3 种分割 s 的方法。
"0|0|00"
"0|00|0"
"00|0|0"

输入：s = "100100010100110"
输出：12

限制

• s[i] == '0' 或者 s[i] == '1'
• 3 <= s.length <= 10^5

算法

(数学) $O(n)$

1. 统计字符串中 1 的个数 ones。
2. 如果 ones 不是 3 的整数倍，直接返回 0。
3. 如果 ones 为 0，则答案为 $(n-1)(n-2)/2$。
4. 接下来，在 1 的个数到达 ones/3 时和 2*ones/3 时，统计 l1 和 l2 分别表示达到个数时持续的长度。根据乘法原理，最终答案为 $l1*l2$。

时间复杂度

• 遍历字符串两次，故总时间复杂度为 $O(n)$。

空间复杂度

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

C++ 代码

#define LL long long

class Solution {
public:
    int numWays(string s) {
        const int mod = 1000000007;
        int n = s.size();
        int ones = 0;

        for (int i = 0; i < n; i++)
            if (s[i] == '1')
                ones++;

        if (ones % 3 != 0)
            return 0;

        if (ones == 0)
            return (LL)(n-1) * (n-2) / 2 % mod;

        ones /= 3;
        int cnt = 0, l1 = 0, l2 = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') cnt++;

            if (cnt == ones) l1++;
            else if (cnt == 2*ones) l2++;
        }

        return (LL)(l1) * l2 % mod;
    }
};