Number of Ways to Split a String

Medium
646.

Number of Ways to Split a String

Number of Ways to Split a String is a medium coding problem on strings, math and counting, asked in Amazon, Google and Goldman Sachs interviews.

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'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var numWays = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Ways to Split a String — Problem & Solution

Number of Ways to Split a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Ways to Split a String is a medium coding problem on strings, math and counting, asked in Amazon, Google and Goldman Sachs interviews.

  • Difficulty: Medium
  • Topics: Strings, Math, Counting
  • Asked at: Amazon, Google, Goldman Sachs
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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'.

Hints for Number of Ways to Split a String

  1. Hint 1

    Count the ones first. If the total is not divisible by 3, the answer is 0.

  2. Hint 2

    The all-zero case is different: the answer is the number of ways to choose two cut points, which is (n-1)(n-2)/2.

  3. Hint 3

    Otherwise the cuts must fall in the run of zeros just after the k-th and 2k-th one. Multiply the two freedoms.

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

Java

public static int numWays(String s) {
    final long MOD = 1000000007L;
    int n = s.length();
    int ones = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '1') ones++;
    }
    if (ones % 3 != 0) return 0;
    if (ones == 0) return (int) (((long) (n - 1) * (n - 2) / 2) % MOD);
    int per = ones / 3;
    long gap1 = 0, gap2 = 0;
    int seen = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '1') seen++;
        else {
            if (seen == per) gap1++;
            if (seen == 2 * per) gap2++;
        }
    }
    return (int) (((gap1 + 1) * (gap2 + 1)) % MOD);
}

C++

int numWays(string s) {
    const long long MOD = 1000000007LL;
    long long n = (long long) s.size();
    long long ones = 0;
    for (char c : s) {
        if (c == '1') ones++;
    }
    if (ones % 3 != 0) return 0;
    if (ones == 0) return (int) (((n - 1) * (n - 2) / 2) % MOD);
    long long per = ones / 3;
    long long gap1 = 0, gap2 = 0, seen = 0;
    for (char c : s) {
        if (c == '1') seen++;
        else {
            if (seen == per) gap1++;
            if (seen == 2 * per) gap2++;
        }
    }
    return (int) (((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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings