Problem

Problem ID: 1573

Title: Number of Ways to Split a String

Difficulty: Medium

Description:

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.

Solution

General Idea

We can solve this by finding the bounds for the first and second segment. However, we will need to handle different cases:

1. Number of ones not divisible by 3
   • Return 0
2. All zeroes
   • No clear difference between the left and right bound
   • Return (n-1)(n-2)/2
3. Everything else
   • Return number of left bounds * number of right bounds

Implementation

class Solution {
public:
    int numWays(string s) {
        size_t n = s.size();
        vector<size_t> pre_ones(n, 0);
        size_t n_ones{0};
        
        for (size_t i = 0; i < n; i++) {
            pre_ones[i] = s[i] - '0';
            if (i > 0) pre_ones[i] += pre_ones[i-1];
            if (s[i] - '0') n_ones++;
        }
        if (n_ones % 3 != 0) return 0;
        size_t l_ones = n_ones/3;
        size_t r_ones = l_ones*2;
        size_t l_n{0};
        size_t r_n{0};
        for (auto bound : pre_ones) {
            if (bound == l_ones) l_n++;
            if (bound == r_ones) r_n++;
        }
        size_t ret_64{0};
        l_n = l_n % static_cast<size_t>(1e9+7);
        r_n = r_n % static_cast<size_t>(1e9+7);
        if (l_ones == r_ones) {
            ret_64 = ((l_n-1)*(l_n -2))/2;
        } else {
            ret_64 = (l_n)*(r_n);
        }
      
        return static_cast<int>(ret_64 % static_cast<size_t>(1e9+7));
    }
};