Number of Ways to Split a String: Counting Splits with Equal Ones
LeetCode Number of Ways to Split a String (Problem 1573) asks you to count the number of ways to split a binary string into three non-empty parts so that each part contains the same number of ones. Return the result modulo 10^9 + 7.
The problem
You are given a binary string s (containing only '0' and '1'). You need to split it into three non-empty contiguous parts s1, s2, s3 (where s = s1 + s2 + s3) such that all three parts have the same number of ones. Return the number of such splits, modulo 10^9 + 7.
For example, given s = "10101", the total number of ones is 3, so each part needs exactly 1 one. There are 4 valid ways to place the two cuts.
The brute force approach
The most direct approach is to try every pair of cut positions. The first cut can go after index 0, 1, ..., n-2, and the second cut goes after some later index. For each pair, you count the ones in each of the three resulting parts and check if they are equal. That gives O(n^2) pairs, and counting ones for each pair takes up to O(n), resulting in O(n^3) time. You can bring this down to O(n^2) with prefix sums, but that is still too slow for strings up to length 100,000.
The key insight
First, count the total number of ones in the string. If this count is not divisible by 3, the answer is immediately 0 because you cannot divide the ones equally.
If the total is 0 (no ones at all), the problem becomes purely combinatorial: you are choosing 2 cut positions out of n - 1 possible gaps, giving C(n-1, 2) = (n-1) * (n-2) / 2.
When the total number of ones is divisible by 3 and greater than 0, each part needs exactly total / 3 ones. The trick is that you do not need to enumerate every pair of cuts. Instead, you find the "gap" of zeros between where the first part's last one ends and the second part's first one begins, and similarly the gap between the second part's last one and the third part's first one. The number of valid first cuts equals the size of the first gap (plus 1, for the positions on either side of the zeros). The number of valid second cuts equals the size of the second gap (plus 1). The answer is the product of these two counts.
Think of it this way: once you know that each part needs k ones, the ones themselves pin down where the boundaries roughly go. The only freedom is in where to place the cuts within the stretches of zeros between the boundary ones. Each gap gives you an independent set of choices, and you multiply them together.
Step-by-step walkthrough
Let's trace through the algorithm on s = "10101". The total number of ones is 3, and each part needs 1 one. We locate the ones, find the two gaps between consecutive groups, and multiply the gap sizes.
Step 1: Count total ones
Total ones = 3. Since 3 % 3 == 0, each part needs exactly 1 one. We proceed to find the gaps.
Step 2: Find the positions of the ones
Ones are at indices 0, 2, 4. The target count per part is 1. We need the boundary after the 1st one and before the 2nd one, and after the 2nd one and before the 3rd one.
Step 3: Identify the first gap
After the 1st one (index 0) and before the 2nd one (index 2), there is 1 zero at index 1. The first cut can go after index 0 or after index 1, giving 2 choices.
Step 4: Identify the second gap
After the 2nd one (index 2) and before the 3rd one (index 4), there is 1 zero at index 3. The second cut can go after index 2 or after index 3, giving 2 choices.
Step 5: Multiply the gap sizes
Gap 1 has 2 choices, gap 2 has 2 choices. Answer = 2 * 2 = 4 (mod 10^9 + 7).
After identifying 2 choices for the first cut and 2 choices for the second cut, we multiply to get 4 total ways.
The code
def numWays(s):
MOD = 10**9 + 7
ones = [i for i, c in enumerate(s) if c == '1']
total = len(ones)
n = len(s)
if total % 3 != 0:
return 0
if total == 0:
return ((n - 1) * (n - 2) // 2) % MOD
k = total // 3
gap1 = ones[k] - ones[k - 1]
gap2 = ones[2 * k] - ones[2 * k - 1]
return (gap1 * gap2) % MOD
The function first collects the indices of all ones. If the count is not divisible by 3, it returns 0. If there are no ones, it returns the combinatorial count C(n-1, 2). Otherwise, it finds the gap between the k-th and (k+1)-th one (where k = total / 3), and the gap between the 2k-th and (2k+1)-th one. These two gap sizes are multiplied together for the final answer.
The gap ones[k] - ones[k - 1] counts how many positions the first cut can occupy. If the k-th one is at index 4 and the (k-1)-th one is at index 2, the gap is 4 - 2 = 2, meaning the cut can go after index 2 or after index 3. That is exactly 2 positions.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force (try all pairs) | O(n^2) | O(1) |
| Prefix sum + two pointers | O(n) | O(n) |
| Gap multiplication | O(n) | O(n) |
The gap multiplication approach scans the string once to collect the positions of ones, then does constant-time arithmetic. The total time is O(n) and space is O(n) for storing the positions. You could reduce space to O(1) by doing two passes instead of storing all positions, but O(n) is clean and well within the constraints.
The building blocks
Divisibility check as early exit
Before doing any real work, you check whether the total count of ones is divisible by 3. This is a common pattern in partition problems: verify the basic feasibility condition first. If the total cannot be evenly divided, no amount of clever cutting will help. This early return saves time and simplifies the rest of the logic.
Combinatorics for the zero-only case
When there are no ones at all, every split is valid because all three parts have zero ones. The number of ways to place two cuts among n - 1 gaps is C(n-1, 2). Recognizing when a problem reduces to a simple combinatorial formula is a valuable skill. It avoids unnecessary iteration and keeps the code compact.
Gap multiplication
The core technique is identifying the "gaps" where cuts can be placed and multiplying the independent choices. This is an application of the multiplication principle from combinatorics: if the first decision has a options and the second has b options, and they are independent, the total is a * b. You will see this pattern in many counting problems where the choices decompose into independent segments.
Edge cases
Total ones not divisible by 3. If the string has 1, 2, 4, 5, or any count of ones that is not a multiple of 3, the answer is 0. The code handles this with an early return.
No ones at all. A string like "0000" has no ones, so every three-way split is valid. The answer is C(n-1, 2). For n = 4, that is 3 * 2 / 2 = 3.
Minimum length string. The string must have at least 3 characters to form three non-empty parts. For s = "000", the answer is 1 (the only split is "0" | "0" | "0").
No zeros between boundary ones. If the ones are packed tightly with no gaps, like s = "111", each gap has size 1, and the answer is 1 * 1 = 1. There is exactly one way to split.
Large gaps of zeros. If the string is s = "1000001000001", the gaps between the groups of ones are large, producing a high count of valid splits. The modular arithmetic ensures the result stays within bounds.
From understanding to recall
The key moment in this problem is recognizing that the answer factors into two independent gap sizes. Many people get stuck trying to enumerate pairs of cuts or building prefix sum arrays with complex conditionals. The leap is seeing that once the ones pin down the rough boundaries, the only freedom is in the zero-filled gaps between those boundaries.
When drilling this problem, focus on three things. First, the divisibility check: can you immediately spot that total % 3 != 0 means the answer is 0? Second, the zero-only special case: do you remember the C(n-1, 2) formula? Third, the gap computation: can you identify which indices to subtract to get the gap sizes without second-guessing yourself?
Also pay attention to the modular arithmetic. Forgetting to mod the result is an easy mistake in contest settings. The multiplication of two gap sizes can overflow in some languages, so applying the mod at the right step matters.
Related posts
- Subarray Sum Equals K - Another counting problem over subarrays. Instead of partitioning by ones, you track prefix sums. Both problems require you to count valid configurations rather than enumerate them.
- Number of 1 Bits - Builds fluency with counting ones in binary representations. Understanding how to efficiently count and locate set bits is foundational for this problem.
- Palindrome Partitioning - A different string partitioning problem. Where this problem uses combinatorics to count splits, palindrome partitioning uses backtracking to enumerate them. Comparing the two helps clarify when counting shortcuts exist.