1678. Number Of Ways To Split A String¶

Difficulty: Medium

1678. Number of Ways to Split a String

Medium

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⁹ + 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 <= 10⁵
s[i] is either '0' or '1'.

Solution¶

class Solution {
    private int pref[];
    private int mod = 1000000007;
    public int numWays(String s) {
        int n = s.length();
        pref = new int[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1')
                pref[i] = 1;
            if (i - 1 >= 0)
                pref[i] += pref[i - 1];
        }

        long ways = 0;
        for (int i = 0; i < n - 2; i++) {
            int leftOnes = pref[i];

            int left = bsLeft(i + 1, n - 2, pref[i]);
            int right = bsRight(i + 1, n - 2, pref[i]);

            if (left == -1 || right == -1)
                continue;
            int rightOnes = pref[n - 1] - pref[right];

            if (rightOnes == leftOnes)
                ways = (ways + right - left + 1) % mod;
        }
        return (int)(ways);
    }

    private int bsLeft(int start, int end, int req) {
        int low = start, high = end;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int total = pref[mid];
            if (start - 1 >= 0)
                total -= pref[start - 1];
            if (total > req)
                high = mid - 1;
            else if (total == req) {
                ans = mid;
                high = mid - 1;
            } else
                low = mid + 1;
        }
        return ans;
    }

    private int bsRight(int start, int end, int req) {
        int low = start, high = end, ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int total = pref[mid];
            if (start - 1 >= 0)
                total -= pref[start - 1];
            if (total > req)
                high = mid - 1;
            else if (total == req) {
                ans = mid;
                low = mid + 1;
            } else
                low = mid + 1;
        }
        return ans;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here