LeetCode Problem 1573

Difficulty: 🟡 Medium
Topics: Math, String

Solution

LeetCode 1573 - Number of Ways to Split a String

Problem Understanding

The problem gives us a binary string s, meaning the string contains only the characters '0' and '1'. We must split this string into exactly three non-empty parts:

• s1
• s2
• s3

These three parts must concatenate back into the original string:

s1 + s2 + s3 = s

The goal is to count how many different ways we can place two split points so that all three resulting substrings contain the same number of '1' characters.

A split is defined by choosing two cut positions in the string. Since all three substrings must be non-empty, the cuts cannot be placed at the very beginning or very end.

For example, if:

s = "10101"

One valid split is:

"1|01|01"

Each substring contains exactly one '1', so this split is valid.

The constraints are important:

• The string length can be as large as 10^5
• A brute-force solution that tries every possible split pair would be too slow
• We need an algorithm close to linear time

The key challenge is efficiently counting valid split positions without explicitly constructing substrings repeatedly.

Several edge cases are especially important:

• The string may contain no '1' characters at all
• The total number of '1' characters may not be divisible by 3
• Large runs of zeros between groups of ones can create multiple valid split positions
• The answer may become very large, so we must return it modulo 10^9 + 7

The problem guarantees:

• The string length is at least 3
• Every character is either '0' or '1'

Approaches

Brute Force Approach

A straightforward approach is to try every possible pair of split positions.

Suppose the string length is n. We can place:

• The first split after index i
• The second split after index j

where:

0 <= i < j < n - 1

For each pair of split positions:

1. Construct the three substrings
2. Count the number of '1' characters in each substring
3. Check whether all three counts are equal
4. Increment the answer if valid

This works because it explicitly checks every possible valid partition.

However, the complexity becomes too large:

• There are O(n^2) possible split pairs
• Counting ones repeatedly can cost O(n)

Even with prefix sums reducing substring counting to O(1), the total complexity is still O(n^2), which is too slow for n = 10^5.

Optimal Approach

The key observation is that the total number of '1' characters completely determines whether a valid split is possible.

Let:

totalOnes = total number of '1' characters

If totalOnes is not divisible by 3, then it is impossible for all three parts to contain the same number of ones.

If:

totalOnes % 3 != 0

the answer is immediately 0.

Otherwise, each substring must contain:

target = totalOnes / 3

ones.

The next important insight is that we do not need to test all split positions individually.

Instead, we locate:

• The boundary between the first and second groups of ones
• The boundary between the second and third groups of ones

Zeros between these boundaries create multiple valid split choices.

If there are:

• a choices for the first split
• b choices for the second split

then the total number of valid partitions is:

a * b

This allows us to solve the problem in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Tries every pair of split positions
Optimal	O(n)	O(n)	Uses positions of ones to count valid split ranges efficiently

Algorithm Walkthrough

Optimal Algorithm

1. Count the total number of '1' characters in the string.

This determines whether an equal split is even possible. 2. If the total number of ones is not divisible by 3, return 0.

Since each substring must contain the same number of ones, divisibility by 3 is mandatory. 3. Handle the special case where the string contains no ones.

If all characters are '0', then every split automatically satisfies the condition because each substring contains zero ones.

Suppose the string length is n.

We need to choose two split positions among the n - 1 possible gaps.

The number of ways is:

$\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$ 4. Otherwise, compute:

target = totalOnes / 3

Each substring must contain exactly target ones. 5. Record the indices where '1' appears.

For example:

s = "10101"
indices = [0, 2, 4]

6. Identify the split boundaries.

The first partition must end somewhere after the target-th one and before the next one.

The number of choices is determined by the zeros between:

• The target-th one
• The (target + 1)-th one

7. Similarly, compute the number of choices for the second split using:

• The (2 * target)-th one
• The (2 * target + 1)-th one

8. Multiply the two counts.

If:

firstChoices = x
secondChoices = y

then:

answer = x * y

9. Return the answer modulo 10^9 + 7.

Why it works

A valid split requires each substring to contain exactly the same number of ones. Once the total number of ones is divisible by 3, the positions of the ones uniquely determine where the partitions may occur.

The only flexibility comes from zeros between critical groups of ones. Any split placed within these zero ranges preserves the required counts. Therefore, the total number of valid splits equals the product of the number of choices for the first and second partition boundaries.

Python Solution

class Solution:
    def numWays(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)

        ones_positions = []

        for index, char in enumerate(s):
            if char == '1':
                ones_positions.append(index)

        total_ones = len(ones_positions)

        if total_ones % 3 != 0:
            return 0

        if total_ones == 0:
            return ((n - 1) * (n - 2) // 2) % MOD

        target = total_ones // 3

        first_gap = (
            ones_positions[target] -
            ones_positions[target - 1]
        )

        second_gap = (
            ones_positions[2 * target] -
            ones_positions[2 * target - 1]
        )

        return (first_gap * second_gap) % MOD

The implementation begins by collecting the indices of every '1' in the string. This gives us direct access to the boundaries between groups of ones.

Next, we compute the total number of ones. If this value is not divisible by three, we immediately return 0.

The special case where the string contains only zeros is handled separately. In that scenario, every split is valid, so we compute the number of ways to choose two split positions from the available gaps.

For the general case, we calculate how many ones must appear in each substring. We then identify the zero gaps between the critical one boundaries.

The value:

ones_positions[target] - ones_positions[target - 1]

represents the number of valid positions for the first split.

Similarly:

ones_positions[2 * target] - ones_positions[2 * target - 1]

represents the number of valid positions for the second split.

Multiplying these values gives the total number of valid partitions.

Go Solution

func numWays(s string) int {
    const MOD int = 1e9 + 7

    n := len(s)
    onesPositions := []int{}

    for i, ch := range s {
        if ch == '1' {
            onesPositions = append(onesPositions, i)
        }
    }

    totalOnes := len(onesPositions)

    if totalOnes%3 != 0 {
        return 0
    }

    if totalOnes == 0 {
        return ((n - 1) * (n - 2) / 2) % MOD
    }

    target := totalOnes / 3

    firstGap := onesPositions[target] - onesPositions[target-1]

    secondGap := onesPositions[2*target] - onesPositions[2*target-1]

    return (firstGap * secondGap) % MOD
}

The Go implementation follows the same logic as the Python solution. The main difference is syntax and slice handling.

Go uses a slice to store the positions of ones. Integer arithmetic is safe here because the maximum answer fits within standard integer limits before modulo reduction.

Unlike Python, Go does not have automatic big integer handling, but the constraints remain small enough for regular integer operations.

Worked Examples

Example 1

s = "10101"

Step 1: Record positions of ones

Index	Character
0	1
1	0
2	1
3	0
4	1

ones_positions = [0, 2, 4]
total_ones = 3

Step 2: Compute target ones per substring

target = 3 / 3 = 1

Each substring must contain exactly one '1'.

Step 3: Compute first split choices

first_gap =
ones_positions[1] - ones_positions[0]
= 2 - 0
= 2

Possible first cuts:

1|0101
10|101

Step 4: Compute second split choices

second_gap =
ones_positions[2] - ones_positions[1]
= 4 - 2
= 2

Possible second cuts:

101|01
1010|1

Step 5: Compute total

2 * 2 = 4

Answer:

4

Example 2

s = "1001"

Step 1: Count ones

total_ones = 2

Step 2: Check divisibility

2 % 3 != 0

Equal partitioning is impossible.

Answer:

0

Example 3

s = "0000"

Step 1: Count ones

total_ones = 0

Step 2: Use combinatorial formula

There are:

n - 1 = 3

possible split positions.

We choose any two.

$\binom{3}{2}=3$

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the string once to collect positions of ones
Space	O(n)	In the worst case, every character is '1'

The algorithm performs a single traversal of the string and stores the indices of all ones. Every later operation is constant time. This makes the solution efficient enough for the maximum input size of 10^5.

Test Cases

class Solution:
    def numWays(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)

        ones_positions = []

        for index, char in enumerate(s):
            if char == '1':
                ones_positions.append(index)

        total_ones = len(ones_positions)

        if total_ones % 3 != 0:
            return 0

        if total_ones == 0:
            return ((n - 1) * (n - 2) // 2) % MOD

        target = total_ones // 3

        first_gap = (
            ones_positions[target] -
            ones_positions[target - 1]
        )

        second_gap = (
            ones_positions[2 * target] -
            ones_positions[2 * target - 1]
        )

        return (first_gap * second_gap) % MOD

sol = Solution()

assert sol.numWays("10101") == 4      # standard example
assert sol.numWays("1001") == 0       # total ones not divisible by 3
assert sol.numWays("0000") == 3       # all zeros case
assert sol.numWays("111") == 1        # exactly one valid split
assert sol.numWays("000") == 1        # smallest all-zero case
assert sol.numWays("110011") == 0     # impossible equal split
assert sol.numWays("10010010") == 0   # total ones not divisible by 3
assert sol.numWays("010010") == 0     # only two ones
assert sol.numWays("100100100") == 1  # clean equal grouping
assert sol.numWays("00100100") == 0   # insufficient divisibility

Test Summary

Test	Why
"10101"	Valid example with multiple split choices
"1001"	Total ones not divisible by 3
"0000"	All-zero special case
"111"	Minimal valid non-zero split
"000"	Smallest possible all-zero input
"110011"	Uneven distribution of ones
"10010010"	Invalid due to divisibility
"010010"	Only two ones in total
"100100100"	Exactly one valid partition
"00100100"	Another invalid divisibility case

Edge Cases

All Characters Are Zero

This is the most important special case. If the string contains no '1' characters, then every split automatically satisfies the condition because all three substrings contain zero ones.

A common bug is forgetting that multiple split combinations are possible even though all substrings are identical in terms of one count. The implementation correctly handles this using the combinatorial formula:

$\binom{n-1}{2}$

Total Number of Ones Is Not Divisible by Three

If the total number of ones cannot be evenly divided into three groups, then no valid split exists.

A naive implementation might still attempt to search for partitions, wasting time or producing incorrect answers. The solution immediately returns 0 in this situation.

Large Zero Gaps Between Ones

Consider a string like:

"1000010000100001"

There may be many valid places to split because zeros between groups of ones can belong to either adjacent substring.

A buggy implementation might count only one split position per boundary. The correct approach counts all possible cuts inside these zero gaps by measuring the distance between critical one indices.