Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s.
Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 109 + 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"
Constraints:
3 <= s.length <= 105s[i] is either '0' or '1'.Problem Overview: Given a binary string s, split it into three non-empty parts so each part contains the same number of '1' characters. Return the number of valid ways to place two split points.
Approach 1: Prefix Sum Counting (O(n) time, O(1) space)
Count the total number of '1' characters first. If the total is not divisible by 3, equal distribution across three parts is impossible, so return 0. Otherwise each segment must contain target = totalOnes / 3. Scan the string while tracking a prefix count of ones. Every index where prefix ones equals target can act as the first cut, and every index where prefix ones equals 2 * target can act as the second cut. Count how many valid first-cut positions appear before valid second-cut positions. This works because the prefix sum directly tells you how many '1' values are included in each segment without recomputing counts. The algorithm runs in O(n) time with O(1) extra space and relies on simple iteration over the string while maintaining a running prefix count similar to a prefix sum technique.
Approach 2: Mathematical Combination (O(n) time, O(1) space)
A special case appears when the string contains zero '1'. Every segment automatically satisfies the condition because each has zero ones. The problem reduces to choosing two split points among the n-1 possible gaps between characters. The number of ways equals C(n-1, 2). For the general case with nonzero ones, identify the positions of the k-th, k+1-th, 2k-th, and 2k+1-th ones (where k = totalOnes / 3). The number of zeros between these boundaries determines how many valid cut positions exist. Multiply the choices for the first and second split to get the final count. This approach uses simple index math and mathematical reasoning rather than maintaining counters during traversal.
Recommended for interviews: The prefix-sum counting approach is the one most interviewers expect. It shows you can translate a counting constraint into prefix state while scanning once through the string. Mentioning the mathematical combination case for totalOnes == 0 demonstrates attention to edge cases and strong problem analysis.
This approach primarily involves the calculation of the number of '1's in the string and then leveraging prefix sums to determine viable partition points:
totalOnes.onesPerPart = totalOnes / 3.firstPartEnds and secondPartStarts.onesPerPart '1's have been seen.The Python solution reads the entire string to count the '1's initially. Using modular arithmetic, if the ones count is zero, it calculates combinations of splitting zeroes correctly. For non-zero ones, it identifies break points based on index locations for effectively segmenting the string post-sufficient counts of '1's.
Python
JavaScript
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) given that extra space used doesn't scale with input size.
This approach uses a combinatorial logic to find the possible splits:
The C++ implementation uses standard library functions to simplify the counting process and leverages modulus arithmetic to handle large output, ensuring integer overflow does not occur.
C++
Time Complexity: O(n), as we process the string linearly.
Space Complexity: O(1), as we only require a fixed count of variables proportionate to input size.
First, we traverse the string s and count the number of characters 1, denoted as cnt. If cnt cannot be divided by 3, then it is impossible to split the string, so we directly return 0. If cnt is 0, it means there are no characters 1 in the string. We can choose any two positions out of n-1 positions to split the string into three substrings, so the number of ways is C_{n-1}^2.
If cnt \gt 0, we update cnt to \frac{cnt}{3}, which is the number of characters 1 in each substring.
Next, we find the minimum index of the right boundary of the first substring, denoted as i_1, and the maximum index of the right boundary of the first substring (exclusive), denoted as i_2. Similarly, we find the minimum index of the right boundary of the second substring, denoted as j_1, and the maximum index of the right boundary of the second substring (exclusive), denoted as j_2. Then the number of ways is (i_2 - i_1) times (j_2 - j_1).
Note that the answer may be very large, so we need to take the modulo 10^9+7.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the string s.
Similar problems:
| Approach | Complexity |
|---|---|
| Prefix Sum Counting | Time Complexity: O(n) where n is the length of the string. |
| Mathematical Combination | Time Complexity: O(n), as we process the string linearly. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum Counting | O(n) | O(1) | General solution. Single pass counting with prefix ones works for all valid cases. |
| Mathematical Combination | O(n) | O(1) | Useful when analyzing positions of the k-th and 2k-th ones or when the string has zero ones. |
number of ways to split a string leetcode | leetcode 1573 | string java • Naresh Gupta • 7,199 views views
Watch 8 more video solutions →Practice Number of Ways to Split a String with our built-in code editor and test cases.
Practice on FleetCode