1573-分割字符串的方案数

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

s2 + s3 = s）。

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

方法一：模拟

要将字符串 s 分割成 3 个非空子字符串，且每个子字符串中的字符 1 的数目相同，显然字符串 s 中的字符 1 的数目必须是 3 的倍数，否则不可能满足 3 个子字符串中的字符 1 的数目相同。当字符串 s 中的字符 1 的数目确定时，每个子字符串中的字符 1 的数目也是确定的。

假设字符串 s 的长度为 n，字符串 s 中的字符 1 的数目为 m。遍历字符串 s，记录每个字符 1 的下标位置，并计算 m 的值。

如果 m 不是 3 的倍数，则不存在符合题目要求的分割 s 的方案，因此返回 0。

如果 m 是 3 的倍数，则分别考虑 m=0 和 m>0 的情况：

如果 m=0，则字符串 s 中的所有字符都为 0，因此可以在 s 的内部的任何位置进行分割。由于 s 的长度为 n，因此有 n-1 个分割位置，选择 2 个不同的分割位置即可将 s 分成 3 个非空子字符串，因此分割 s 的方案数为 \binom{n-1/2}=(n-1)(n-2)}{2。
如果 m>0，则每个子字符串都包含 m/3 个字符 1。假设 3 个子字符串从左到右依次为 s_1、s_2、s_3，其中 s_1 的最后一个字符 1 和 s_2 的第一个字符 1 之间的距离为 count}_1，s_2 的最后一个字符 1 和 s_3 的第一个字符 1 之间的距离为 count}_2，则对应的两个字符 1 之间的字符 0 的个数分别为 count}_1-1 和 count}_2-1，分别有 count}_1 和 count}_2 个分割位置，因此分割 s 的方案数为 count}_1 \times \textit{count}_2。

[sol1-Java]class Solution {
    public int numWays(String s) {
        final int MODULO = 1000000007;
        List<Integer> ones = new ArrayList<Integer>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                ones.add(i);
            }
        }
        int m = ones.size();
        if (m % 3 != 0)
            return 0;
        if (m == 0) {
            long ways = (long) (n - 1) * (n - 2) / 2;
            return (int) (ways % MODULO);
        } else {
            int index1 = m / 3, index2 = m / 3 * 2;
            int count1 = ones.get(index1) - ones.get(index1 - 1);
            int count2 = ones.get(index2) - ones.get(index2 - 1);
            long ways = (long) count1 * count2;
            return (int) (ways % MODULO);
        }
    }
}

[sol1-C++]class Solution {
private:
    static constexpr int MODULO = 1000000007;

public:
    int numWays(string s) {
        vector<int> ones;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                ones.push_back(i);
            }
        }
        
        int m = ones.size();
        if (m % 3 != 0) {
            return 0;
        }
        if (m == 0) {
            long long ways = (long long)(n - 1) * (n - 2) / 2;
            return ways % MODULO;
        }
        else {
            int index1 = m / 3, index2 = m / 3 * 2;
            int count1 = ones[index1] - ones[index1 - 1];
            int count2 = ones[index2] - ones[index2 - 1];
            long long ways = (long long)count1 * count2;
            return ways % MODULO;
        }
    }
};

[sol1-Python3]class Solution:
    def numWays(self, s: str) -> int:
        MODULO = 1000000007

        ones = list()
        n = len(s)
        for i, digit in enumerate(s):
            if digit == "1":
                ones.append(i)
        
        m = len(ones)
        if m % 3 != 0:
            return 0
        
        if m == 0:
            ways = (n - 1) * (n - 2) // 2
            return ways % MODULO
        else:
            index1, index2 = m // 3, m // 3 * 2;
            count1 = ones[index1] - ones[index1 - 1]
            count2 = ones[index2] - ones[index2 - 1]
            ways = count1 * count2
            return ways % MODULO

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。遍历字符串一次，得到所有字符 1 的下标位置，然后计算分割字符串的方案数，上述操作的时间复杂度都是 O(1)。
空间复杂度：O(n)，其中 n 是字符串 s 的长度。需要记录每个字符 1 的下标位置，字符 1 的个数不会超过字符串的长度。