Number of Ways to Split a String - Video Solutions
number of ways to split a string leetcode | leetcode 1573 | string java
Number of Ways to Split a String - Video Solution
Watch 8 video solutions for Number of Ways to Split a String, a medium level problem involving Math, String. This walkthrough by Naresh Gupta has 7,267 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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'.
Approach Overview
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.
Complexity Analysis
| 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. |