class Solution:
def numWays(self, s: str) -> int:
MOD = 10**9 + 7
total_ones = s.count('1')
n = len(s)
if total_ones == 0:
# All zeros: choose any 2 cuts from n-1 positions
return ((n - 1) * (n - 2) // 2) % MOD
if total_ones % 3 != 0:
return 0
ones_per_part = total_ones // 3
first, second = -1, -1
ones_count = 0
# Find the number of zeros after first and second cuts
first_cut_zeros = second_cut_zeros = 0
for i, ch in enumerate(s):
if ch == '1':
ones_count += 1
if ones_count == ones_per_part and first == -1:
first = i
if ones_count == ones_per_part + 1 and second == -1:
first_cut_zeros = i - first - 1
second = i
if ones_count == 2 * ones_per_part and second_cut_zeros == 0 and i > second:
second_cut_zeros = i - second - 1
return ((first_cut_zeros + 1) * (second_cut_zeros + 1)) % MOD
class Solution {
public:
int numWays(string s) {
const int MOD = 1e9 + 7;
int n = s.size();
int totalOnes = 0;
for(char c : s) if(c == '1') totalOnes++;
if(totalOnes == 0) {
// All zeros: choose any 2 cuts from n-1 positions
long long cuts = (long long)(n - 1) * (n - 2) / 2;
return (int)(cuts % MOD);
}
if(totalOnes % 3 != 0) return 0;
int onesPerPart = totalOnes / 3;
int onesCount = 0, first = -1, second = -1;
long long firstCutZeros = 0, secondCutZeros = 0;
for(int i = 0; i < n; ++i) {
if(s[i] == '1') onesCount++;
if(onesCount == onesPerPart && first == -1) first = i;
if(onesCount == onesPerPart + 1 && second == -1) {
firstCutZeros = i - first - 1;
second = i;
}
if(onesCount == 2 * onesPerPart && secondCutZeros == 0 && i > second) {
secondCutZeros = i - second - 1;
}
}
return (int)(((firstCutZeros + 1) * (secondCutZeros + 1)) % MOD);
}
};
class Solution {
public int numWays(String s) {
int MOD = 1000000007;
int n = s.length();
int totalOnes = 0;
for (char c : s.toCharArray()) if (c == '1') totalOnes++;
if (totalOnes == 0) {
long cuts = (long)(n - 1) * (n - 2) / 2;
return (int)(cuts % MOD);
}
if (totalOnes % 3 != 0) return 0;
int onesPerPart = totalOnes / 3;
int onesCount = 0, first = -1, second = -1;
long firstCutZeros = 0, secondCutZeros = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '1') onesCount++;
if (onesCount == onesPerPart && first == -1) first = i;
if (onesCount == onesPerPart + 1 && second == -1) {
firstCutZeros = i - first - 1;
second = i;
}
if (onesCount == 2 * onesPerPart && secondCutZeros == 0 && i > second) {
secondCutZeros = i - second - 1;
}
}
return (int)(((firstCutZeros + 1) * (secondCutZeros + 1)) % MOD);
}
}
var numWays = function(s) {
const MOD = 1e9 + 7;
const n = s.length;
let totalOnes = 0;
for (let ch of s) if (ch === '1') totalOnes++;
if (totalOnes === 0) {
return ((n - 1) * (n - 2) / 2) % MOD;
}
if (totalOnes % 3 !== 0) return 0;
let onesPerPart = totalOnes / 3;
let onesCount = 0, first = -1, second = -1;
let firstCutZeros = 0, secondCutZeros = 0;
for (let i = 0; i < n; i++) {
if (s[i] === '1') onesCount++;
if (onesCount === onesPerPart && first === -1) first = i;
if (onesCount === onesPerPart + 1 && second === -1) {
firstCutZeros = i - first - 1;
second = i;
}
if (onesCount === 2 * onesPerPart && secondCutZeros === 0 && i > second) {
secondCutZeros = i - second - 1;
}
}
return ((firstCutZeros + 1) * (secondCutZeros + 1)) % MOD;
};
Given a binary string s, you are asked to split it into three non-empty parts such that each part contains the same number of '1's.
Return the number of ways you can split s into these three parts. Since the answer may be very large, return it modulo 10^9 + 7.
s (no reordering).s as described, return 0.
For example, given s = "10101", the answer is 4.
The first instinct might be to try all possible ways to split the string at two different points and check if each part has the same number of '1's. However, this brute-force approach is inefficient for large strings.
We notice that the only thing that matters is the count of '1's in each part. If the total number of '1's in s is not divisible by 3, it's impossible to split. If there are no '1's at all, then every split is valid as long as the parts are non-empty.
For the general case, we need to find positions to cut so that each part has exactly one-third of the total '1's. The number of ways to split is determined by the number of zeros between these cut points, because zeros do not affect the count of '1's.
s. Let this be totalOnes.
totalOnes is 0, then the string is all zeros. The number of ways to split is the number of ways to choose 2 cut points from n-1 possible cut positions: ((n-1) * (n-2)) / 2.
totalOnes % 3 != 0, return 0. It's impossible to split evenly.
onesPerPart = totalOnes / 3.
onesPerPart-th '1') and the start of the next '1' (this is the number of possible first cuts).
2 * onesPerPart-th '1') and the start of the next '1' (number of possible second cuts).
10^9 + 7.
This approach avoids brute-force and leverages the properties of the string to achieve an efficient solution.
Let's use s = "10101" as an example.
2 * 2 = 4 ways to split.
n.
The key insight is that the solution depends on counting '1's and zeros, not on the actual arrangement of the string. By focusing on the zeros between the required '1's, we can efficiently compute the number of valid splits without brute-force. This approach is both efficient and elegant, leveraging properties of combinatorics and string processing.