Formatted question description: https://leetcode.ca/all/1573.html

# 1573. Number of Ways to Split a String (Medium)

Given a binary string `s`

(a string consisting only of '0's and '1's), we can split `s`

into 3 **non-empty** strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways `s`

can be split such that the number of characters '1' is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 7.

**Example 1:**

Input:s = "10101"Output:4Explanation:There are four ways to split s in 3 parts where each part contain the same number of letters '1'. "1|010|1" "1|01|01" "10|10|1" "10|1|01"

**Example 2:**

Input:s = "1001"Output:0

**Example 3:**

Input:s = "0000"Output:3Explanation:There are three ways to split s in 3 parts. "0|0|00" "0|00|0" "00|0|0"

**Example 4:**

Input:s = "100100010100110"Output:12

**Constraints:**

`s[i] == '0'`

or`s[i] == '1'`

`3 <= s.length <= 10^5`

**Related Topics**:

String

**Similar Questions**:

## Solution 1.

First count the number of 1s. The the count is not divisible by 3, we can’t split `s`

into 3 parts, then return `0`

.

If `cnt == 0`

, what we need to do is to choose `2`

out of the `N - 1`

gaps between the `N`

elements to split the `s`

, so there are `combination(N - 1, 2) = (N - 1) * (N - 2) / 2`

cases.

Othewise, we need to find the number of possible cases of `s1`

and `s3`

respectively.

For `s1`

, that’s the number of `0`

s between the `cnt/3`

-th (1-based) and `cnt/3 + 1`

-th `1`

from the left side, plus `1`

. Let this be `left`

.

For `s3`

, that’s the number of `0`

s between the `cnt/3`

-th (1-based) and `cnt/3 + 1`

-th `1`

from the right side, plus `1`

. Let this be `right`

.

And the answer is different combinations of `left`

and `right`

and thus is `left * right`

.

```
// OJ: https://leetcode.com/problems/number-of-ways-to-split-a-string/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numWays(string s) {
long mod = 1e9+7, cnt = 0;
for (char c : s) cnt += c == '1'; // cnt is the count of all 1s
if (cnt % 3) return 0; // if cnt is not divisible by 3, we can't split the string into 3 parts, return 0
if (cnt == 0) return (long)(s.size() - 1) * (s.size() - 2) / 2 % mod; // if cnt is 0, there are (N - 1) * (N - 2) / 2 cases.
int i = 0, c = 0, left = 0, right = 0; // left and right are the numbers of possible cases for s1 and s2 respectively
while (c <= cnt / 3) {
c += s[i++] == '1';
if (c == cnt / 3) ++left;
}
i = s.size() - 1, c = 0;
while (c <= cnt / 3) {
c += s[i--] == '1';
if (c == cnt / 3) ++right;
}
return (long)left * right % mod; // The answer is simply left * right
}
};
```

Java

```
class Solution {
public int numWays(String s) {
final int MODULO = 1000000007;
List<Integer> ones = new ArrayList<Integer>();
int length = s.length();
for (int i = 0; i < length; i++) {
if (s.charAt(i) == '1')
ones.add(i);
}
int size = ones.size();
if (size % 3 != 0)
return 0;
if (size == 0) {
long ways = (long) (length - 1) * (length - 2) / 2;
return (int) (ways % MODULO);
} else {
int index1 = size / 3, index2 = size / 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);
}
}
}
```