# Number of Ways to Split a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-ways-to-split-a-string)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-split-a-string
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
---
## Problem
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'`.

# Approaches
## Brute Force
This approach exhaustively checks every possible way to split the string into three non-empty parts. It uses nested loops to define the two cut points and then, for each split, counts the number of '1's in each of the three resulting substrings to see if they are equal.
**Time:** O(N^3), where N is the length of the string. The two nested loops run in O(N^2), and inside the loops, creating and counting ones in substrings takes O(N) time. · **Space:** O(N), where N is the length of the string. This is due to the creation of substrings in each iteration.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient due to its O(N^3) time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The algorithm iterates through all possible pairs of cut points `(i, j)`. The first cut is after index `i` and the second after index `j`. The loops ensure that `0 <= i < j < n-1`, which guarantees three non-empty substrings: `s1 = s[0...i]`, `s2 = s[i+1...j]`, and `s3 = s[j+1...n-1]`. For each such split, we manually count the '1's in `s1`, `s2`, and `s3`. If the counts are equal, we increment a result counter. This method is simple to understand but highly inefficient due to the repeated counting within the nested loops.

```java
class Solution {
    public int numWays(String s) {
        int n = s.length();
        long ways = 0;
        int MOD = 1_000_000_007;

        // i is the end index of s1
        for (int i = 0; i < n - 2; i++) {
            // j is the end index of s2
            for (int j = i + 1; j < n - 1; j++) {
                String s1 = s.substring(0, i + 1);
                String s2 = s.substring(i + 1, j + 1);
                String s3 = s.substring(j + 1);

                int ones1 = countOnes(s1);
                int ones2 = countOnes(s2);
                int ones3 = countOnes(s3);

                if (ones1 == ones2 && ones2 == ones3) {
                    ways++;
                }
            }
        }
        return (int) (ways % MOD);
    }

    private int countOnes(String str) {
        int count = 0;
        for (char c : str.toCharArray()) {
            if (c == '1') {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `ways` to 0.
- Use a nested loop structure to iterate through all possible pairs of cut points. The outer loop for the first cut `i` runs from `0` to `n-3`, and the inner loop for the second cut `j` runs from `i+1` to `n-2`.
- For each pair `(i, j)`, split the string `s` into three substrings: `s1 = s.substring(0, i + 1)`, `s2 = s.substring(i + 1, j + 1)`, and `s3 = s.substring(j + 1)`.
- Create a helper function `countOnes` to count the number of '1's in a string.
- Call `countOnes` for `s1`, `s2`, and `s3`.
- If the counts are equal, increment the `ways` counter.
- After the loops complete, return `ways`.

## Brute Force with Prefix Sums
This approach improves upon the brute-force method by pre-calculating the number of '1's up to each index using a prefix sum array. This allows for O(1) lookup of the number of '1's in any substring, reducing the overall complexity from cubic to quadratic.
**Time:** O(N^2). The pre-computation of prefix sums takes O(N), but the dominant part is the nested loops which run in O(N^2). · **Space:** O(N) to store the prefix sum array.
**Pros:** Faster than the naive brute-force approach.; Introduces a common optimization technique (prefix sums).
**Cons:** Still too slow for the given constraints. An O(N^2) solution will time out when N is up to 10^5.
### Explanation
We first create a prefix sum array, `prefixOnes`, where `prefixOnes[i]` stores the total count of '1's in the substring `s[0...i-1]`. This array can be built in a single pass (O(N)). After this pre-computation, we use the same nested loop structure as the brute-force approach to iterate through all possible split points `(i, j)`. However, instead of re-counting '1's for each substring, we use the `prefixOnes` array to find the counts in O(1) time. This optimization significantly improves performance, but it's not sufficient for the problem's constraints.

```java
class Solution {
    public int numWays(String s) {
        int n = s.length();
        int MOD = 1_000_000_007;

        int[] prefixOnes = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixOnes[i + 1] = prefixOnes[i] + (s.charAt(i) - '0');
        }

        long ways = 0;
        int totalOnes = prefixOnes[n];

        // i is the end index of s1
        for (int i = 0; i < n - 2; i++) {
            // j is the end index of s2
            for (int j = i + 1; j < n - 1; j++) {
                int ones1 = prefixOnes[i + 1];
                int ones2 = prefixOnes[j + 1] - prefixOnes[i + 1];
                // ones3 can be calculated without another lookup
                int ones3 = totalOnes - prefixOnes[j + 1];

                if (ones1 == ones2 && ones2 == ones3) {
                    ways++;
                }
            }
        }
        return (int) (ways % MOD);
    }
}
```
### Algorithm
- Create a prefix sum array `prefixOnes` of size `n+1`.
- Iterate through the input string `s` from `i = 0` to `n-1`, populating `prefixOnes[i+1]` with `prefixOnes[i] + (s.charAt(i) == '1' ? 1 : 0)`.
- Initialize a counter `ways` to 0.
- Use the same nested loop structure as the brute-force approach to iterate through all cut points `(i, j)`.
- Inside the loops, calculate the number of '1's in each part in O(1) time using the `prefixOnes` array:
  - `ones1 = prefixOnes[i+1]`
  - `ones2 = prefixOnes[j+1] - prefixOnes[i+1]`
  - `ones3 = prefixOnes[n] - prefixOnes[j+1]`
- If `ones1`, `ones2`, and `ones3` are equal, increment `ways`.
- Return `ways` after the loops.

## Combinatorial Single Pass Approach
This is the most efficient approach, solving the problem in linear time. It relies on a key insight: if the total number of '1's is `C`, each of the three parts must have `C/3` ones. The problem then reduces to a combinatorial task of finding how many ways we can place the two cuts to satisfy this condition.
**Time:** O(N), as we iterate through the string a constant number of times (at most two passes). · **Space:** O(1), as we only use a few variables to store counts, regardless of the input size.
**Pros:** Highly efficient with linear time complexity, passing all constraints.; Low constant space usage.
**Cons:** The logic is more complex than brute-force, requiring careful handling of edge cases like the all-zeros string.
### Explanation
1.  First, we count the total number of '1's in the string, `totalOnes`.
2.  A valid split is only possible if `totalOnes` is a multiple of 3. If not, we immediately return 0.
3.  We handle the special case where `totalOnes` is 0. If the string contains no '1's, any split into three non-empty parts is valid. The problem becomes choosing 2 cut positions from the `n-1` available gaps between characters. The number of ways is given by the combination formula `C(n-1, 2) = (n-1) * (n-2) / 2`.
4.  For the general case (`totalOnes > 0`), let `k = totalOnes / 3`. The first part `s1` must contain `k` ones, and the second part `s2` must also contain `k` ones. This means the first cut must be placed after the `k`-th '1' but before the `(k+1)`-th '1'. The number of possible positions for the first cut (`ways1`) is the number of zeros between the `k`-th and `(k+1)`-th '1's, plus one. Similarly, the number of positions for the second cut (`ways2`) is determined by the zeros between the `2k`-th and `(2k+1)`-th '1's. We can find `ways1` and `ways2` in a single pass by counting the number of indices where the prefix of the string contains exactly `k` ones and `2k` ones, respectively.

```java
class Solution {
    public int numWays(String s) {
        int n = s.length();
        int MOD = 1_000_000_007;
        
        int totalOnes = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                totalOnes++;
            }
        }

        if (totalOnes % 3 != 0) {
            return 0;
        }

        if (totalOnes == 0) {
            // Choose 2 cut positions from n-1 gaps: C(n-1, 2)
            long ways = (long)(n - 1) * (n - 2) / 2;
            return (int)(ways % MOD);
        }

        int onesPerPart = totalOnes / 3;
        long ways1 = 0;
        long ways2 = 0;
        int currentOnes = 0;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                currentOnes++;
            }
            // Count valid positions for the first cut
            if (currentOnes == onesPerPart) {
                ways1++;
            }
            // Count valid positions for the second cut
            else if (currentOnes == 2 * onesPerPart) {
                ways2++;
            }
        }
        
        long result = (ways1 * ways2) % MOD;
        return (int) result;
    }
}
```
### Algorithm
- First, iterate through the string to count the total number of '1's, `totalOnes`.
- If `totalOnes` is not divisible by 3, return 0, as an equal split is impossible.
- **Case 1: `totalOnes == 0`**. The string consists only of '0's. Any split is valid. We need to choose 2 cut positions from `n-1` available gaps. The number of ways is `C(n-1, 2) = (n-1) * (n-2) / 2`. Calculate this value modulo `10^9 + 7`.
- **Case 2: `totalOnes > 0`**. Let `k = totalOnes / 3`. We need to find the number of ways to place the first cut and the second cut.
  - The first cut can be placed anywhere between the `k`-th '1' and the `(k+1)`-th '1'.
  - The second cut can be placed anywhere between the `2k`-th '1' and the `(2k+1)`-th '1'.
- Initialize `ways1 = 0`, `ways2 = 0`, and `currentOnes = 0`.
- Iterate through the string one more time. If `s[i] == '1'`, increment `currentOnes`.
- If `currentOnes == k`, we are in a valid region for the first cut. Increment `ways1`.
- If `currentOnes == 2k`, we are in a valid region for the second cut. Increment `ways2`.
- The total number of ways is `(ways1 * ways2)`. Return this product modulo `10^9 + 7`. Use `long` for the multiplication to prevent overflow.

# Solutions
### Java

```java
class Solution {
private
  String s;
public
  int numWays(String s) {
    this.s = s;
    int cnt = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '1') {
        ++cnt;
      }
    }
    int m = cnt % 3;
    if (m != 0) {
      return 0;
    }
    final int mod = (int)1 e9 + 7;
    if (cnt == 0) {
      return (int)(((n - 1L) * (n - 2) / 2) % mod);
    }
    cnt /= 3;
    long i1 = find(cnt), i2 = find(cnt + 1);
    long j1 = find(cnt * 2), j2 = find(cnt * 2 + 1);
    return (int)((i2 - i1) * (j2 - j1) % mod);
  }
private
  int find(int x) {
    int t = 0;
    for (int i = 0;; ++i) {
      t += s.charAt(i) == '1' ? 1 : 0;
      if (t == x) {
        return i;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numWays(string s) {
    int cnt = 0;
    for (char &c : s) {
      cnt += c == '1';
    }
    int m = cnt % 3;
    if (m) {
      return 0;
    }
    const int mod = 1e9 + 7;
    int n = s.size();
    if (cnt == 0) {
      return (n - 1LL) * (n - 2) / 2 % mod;
    }
    cnt /= 3;
    auto find = [&](int x) {
      int t = 0;
      for (int i = 0;; ++i) {
        t += s[i] == '1';
        if (t == x) {
          return i;
        }
      }
    };
    int i1 = find(cnt), i2 = find(cnt + 1);
    int j1 = find(cnt * 2), j2 = find(cnt * 2 + 1);
    return (1LL * (i2 - i1) * (j2 - j1)) % mod;
  }
};

```

### Python

```python
class Solution:
    def numWays(self, s: str) -> int: def find(x): t = 0 for i, c in enumerate(s): t += int(c == '1') if t == x: return i cnt, m = divmod(sum(c == '1' for c in s), 3) if m: return 0 n = len(s) mod = 10 ** 9 + 7 if cnt == 0: return ((n - 1) * (n - 2) // 2) % mod i1, i2 = find(cnt), find(cnt + 1) j1, j2 = find(cnt * 2), find(cnt * 2 + 1) return (i2 - i1) * (j2 - j1) % (10 ** 9 + 7)

```