Skip to main content
Talentd

Number of Ways to Split a String - Solution & Explanation

MediumMathString14 min readAsked at: Microsoft
Practice this problem

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 <= 105
  • s[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.

Approach 1: Prefix Sum Counting

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:

  • First, count the total number of '1's in the string. If this number is not divisible by 3, return 0 as it's impossible to split the string as required. Let's denote the total number of '1's as totalOnes.
  • Compute the number of '1's that each partition should have: onesPerPart = totalOnes / 3.
  • Traverse the string to count where these partitions can occur. Maintain two counts: firstPartEnds and secondPartStarts.
  • For the first partition, count how many ending points there are at the point where exactly onesPerPart '1's have been seen.
  • Similarly, for the second partition, count how many starting points there are after the first partition where the same condition holds.
  • The number of ways to split is the product of these two counts.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Mathematical Combination

This approach uses a combinatorial logic to find the possible splits:

  • Calculate the total number of '1's and ensure it's divisible by 3; otherwise, return 0.
  • For a case with zero '1's, the potential splits are computed using combinatorial mathematics regarding zero positions.
  • Divide the task into finding partitions that place the required '1's in each segment based logically on zero interspersal between calculated divisions.
  • Combining counts of zero placement spans for multiplicity represents valid configurations for splitting.

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.

Code

C++

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Counting

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:

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum Counting

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.

Mathematical Combination

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.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Sum CountingO(n)O(1)General solution. Single pass counting with prefix ones works for all valid cases.
Mathematical CombinationO(n)O(1)Useful when analyzing positions of the k-th and 2k-th ones or when the string has zero ones.

Video Solution

number of ways to split a string leetcode | leetcode 1573 | string java • Naresh Gupta • 7,267 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Number of Ways to Split a String easy or hard?
The problem is rated Medium on LeetCode. The logic becomes straightforward once you recognize that each segment must contain totalOnes/3 ones and that valid splits correspond to specific prefix counts.
Number of Ways to Split a String Python/Java solution
Most implementations iterate through the string, count total ones, and track prefix counts. Python or Java solutions maintain counters for when prefix ones equal target and 2×target, producing an O(n) time and O(1) space implementation.
How to solve Number of Ways to Split a String in O(n)?
First count the total number of '1's. If it is not divisible by three, return 0. Otherwise scan the string and track prefix ones; positions where the count equals total/3 represent valid first cuts and positions where it equals 2×(total/3) represent valid second cuts. Multiply the number of available gaps to compute the total ways.
What is the best approach for Number of Ways to Split a String?
The optimal approach uses prefix counting of '1's while scanning the string once. After verifying the total number of ones is divisible by three, count valid positions where the prefix contains target and 2×target ones. This produces the number of valid first and second split points in O(n) time and O(1) space.
Is Number of Ways to Split a String asked at Google/Amazon/Meta?
Problems involving prefix counting, combinatorics, and string partitioning are common in interviews at companies like Google, Amazon, and Meta. Variants of this problem appear in interview prep platforms and coding assessments because they test counting logic and edge-case handling.
What data structure is used in Number of Ways to Split a String?
The problem mainly uses counters and prefix sums while iterating through a string. No advanced data structure is required; a few integer variables track the number of '1's and valid split positions.
What is the time complexity of Number of Ways to Split a String?
The optimal solution runs in O(n) time because the string is scanned once to count ones and determine valid split positions. Space complexity is O(1) since only a few counters are maintained regardless of input size.

Ready to solve this problem?

Practice Number of Ways to Split a String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Split Array with Equal Sum