Number of Ways to Split a String — Medium Problem & Solution

Problem statement

Given a binary string s, split it into three non-empty parts s1 + s2 + s3 so that each part contains the same number of '1' characters.

Return how many such splits exist, modulo 10^9 + 7.

Example 1

Input: s = "10101"
Output: 4
Explanation: Each part must hold exactly one 1; there are four valid cut placements.

Example 2

Input: s = "1001"
Output: 0
Explanation: Two ones cannot be shared equally among three parts.

Example 3

Input: s = "0000"
Output: 3
Explanation: With no ones at all, any two of the three cut positions work.

Constraints

• 3 <= s.length <= 100000
• s[i] is '0' or '1'.

How to solve Number of Ways to Split a String

The positions of the ones fix where the cuts may go. Between the k-th and (k+1)-th one there is a run of zeros, and the cut may land anywhere inside it — the number of choices is that run's length plus one. The two cuts are independent, so the answers multiply.

Approach

1. Count the total number of ones. If it is not a multiple of 3, return 0.
2. If there are no ones, every pair of distinct cut positions works: return (n-1)(n-2)/2 mod 1e9+7.
3. Otherwise let per = ones / 3. Sweep the string counting ones seen so far; each '0' encountered while exactly per ones have been seen is one extra placement for the first cut, and each '0' at exactly 2 * per ones is one for the second.
4. Return (gap1 + 1) * (gap2 + 1) mod 1e9+7.

Why it works

Every valid split assigns the first per ones to s1, the next per to s2 and the rest to s3. The first cut must sit after the per-th one and before the (per+1)-th, so it has exactly one position per zero in between, plus the position immediately after that one. The same holds for the second cut, and the two ranges are disjoint, so the choices are independent.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Forgetting the all-zero case, which the gap formula does not cover.
• Overflow: (gap1 + 1) * (gap2 + 1) can exceed 32 bits before the modulo, so use a 64-bit intermediate.
• (n-1)(n-2)/2 must be reduced modulo after the division, not before.

Reference solution

Python

def numWays(s: str) -> int:
    MOD = 1000000007
    n = len(s)
    ones = s.count("1")
    if ones % 3 != 0:
        return 0
    if ones == 0:
        return ((n - 1) * (n - 2) // 2) % MOD
    per = ones // 3
    gap1 = gap2 = 0
    seen = 0
    for c in s:
        if c == "1":
            seen += 1
        else:
            if seen == per:
                gap1 += 1
            if seen == 2 * per:
                gap2 += 1
    return ((gap1 + 1) * (gap2 + 1)) % MOD

JavaScript

var numWays = function(s) {
    var MOD = 1000000007;
    var n = s.length, ones = 0;
    for (var i = 0; i < n; i++) {
        if (s.charAt(i) === "1") ones++;
    }
    if (ones % 3 !== 0) return 0;
    if (ones === 0) return (((n - 1) * (n - 2)) / 2) % MOD;
    var per = ones / 3;
    var gap1 = 0, gap2 = 0, seen = 0;
    for (var j = 0; j < n; j++) {
        if (s.charAt(j) === "1") seen++;
        else {
            if (seen === per) gap1++;
            if (seen === 2 * per) gap2++;
        }
    }
    return ((gap1 + 1) * (gap2 + 1)) % MOD;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium