Number of ways to split a string

Math String

34.5% acceptance

Feb 25, 2026

767

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 10^9 + 7.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_ways(s: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let s: Vec<char> = s.chars().collect();
    let n = s.len();
    let total_ones: i64 = s.iter().filter(|&&c| c == '1').count() as i64;

    if total_ones % 3 != 0 {
      return 0;
    }

    if total_ones == 0 {
      // Choose 2 split points among n-1 gaps: C(n-1, 2)
      let gaps = (n - 1) as i64;
      return ((gaps * (gaps - 1) / 2) % MOD) as i32;
    }

    let per_part = total_ones / 3;
    // Find positions of the per_part-th, (per_part+1)-th, (2*per_part)-th, (2*per_part+1)-th ones
    let mut ones_pos = Vec::new();
    for (i, &c) in s.iter().enumerate() {
      if c == '1' {
        ones_pos.push(i as i64);
      }
    }

    // First split: between ones_pos[per_part-1] and ones_pos[per_part]
    // Second split: between ones_pos[2*per_part-1] and ones_pos[2*per_part]
    let gap1 = (ones_pos[per_part as usize] - ones_pos[per_part as usize - 1]) as i64;
    let gap2 = (ones_pos[2 * per_part as usize] - ones_pos[2 * per_part as usize - 1]) as i64;

    ((gap1 % MOD) * (gap2 % MOD) % MOD) as i32
  }
}