##### Welcome to Subscribe On Youtube

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: 4
Explanation: 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: 3
Explanation: 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 0s 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 0s 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
}
};

• 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')
}
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);
}
}
}

############

class Solution {
private String s;

public int numWays(String s) {
this.s = s;
int cnt = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '1') {
++cnt;
}
}
int m = cnt % 3;
if (m != 0) {
return 0;
}
final int mod = (int) 1e9 + 7;
if (cnt == 0) {
return (int) (((n - 1L) * (n - 2) / 2) % mod);
}
cnt /= 3;
long i1 = find(cnt), i2 = find(cnt + 1);
long j1 = find(cnt * 2), j2 = find(cnt * 2 + 1);
return (int) ((i2 - i1) * (j2 - j1) % mod);
}

private int find(int x) {
int t = 0;
for (int i = 0;; ++i) {
t += s.charAt(i) == '1' ? 1 : 0;
if (t == x) {
return i;
}
}
}
}

• // 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
}
};

• class Solution:
def numWays(self, s: str) -> int:
def find(x):
t = 0
for i, c in enumerate(s):
t += int(c == '1')
if t == x:
return i

cnt, m = divmod(sum(c == '1' for c in s), 3)
if m:
return 0
n = len(s)
mod = 10**9 + 7
if cnt == 0:
return ((n - 1) * (n - 2) // 2) % mod
i1, i2 = find(cnt), find(cnt + 1)
j1, j2 = find(cnt * 2), find(cnt * 2 + 1)
return (i2 - i1) * (j2 - j1) % (10**9 + 7)


• func numWays(s string) int {
cnt := 0
for _, c := range s {
if c == '1' {
cnt++
}
}
m := cnt % 3
if m != 0 {
return 0
}
const mod = 1e9 + 7
n := len(s)
if cnt == 0 {
return (n - 1) * (n - 2) / 2 % mod
}
cnt /= 3
find := func(x int) int {
t := 0
for i := 0; ; i++ {
if s[i] == '1' {
t++
if t == x {
return i
}
}
}
}
i1, i2 := find(cnt), find(cnt+1)
j1, j2 := find(cnt*2), find(cnt*2+1)
return (i2 - i1) * (j2 - j1) % mod
}