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:
3 <= s.length <= 10^5
s[i] is '0' or '1'.
class Solution {
long mod = 1_000_000_007;
public long length(String s, int index, int sum) {
if (index == 0) {
boolean found = false;
long len = 0, count = 0;
while (index < s.length()) {
if (s.charAt(index) == '1') {
if (found)
break;
count++;
if (count == sum)
found = true;
}
if (found)
len++;
index++;
}
return len;
} else {
boolean found = false;
int len = 0, count = 0;
while (index >= 0) {
if (s.charAt(index) == '1') {
if (found)
break;
count++;
if (count == sum)
found = true;
}
if (found)
len++;
index--;
}
return len;
}
}
public int numWays(String s) {
int nums = 0;
for (char c : s.toCharArray())
if (c == '1')
nums++;
if (nums % 3 != 0)
return 0;
if (nums == 0) {
long len = s.length() - 2;
return (int) ((len * (len + 1L) / 2L) % mod);
}
// Find out the 4 positions we need (because 2 are fixed i.e start & end of s1 & s3 resp.)
return (int) ((length(s, 0, nums / 3) * length(s, s.length() - 1, nums / 3)) % mod);
}
}