1573. Number of Ways to Split a String

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

Solutions

Solution 1: Counting

First, we traverse the string \(s\) and count the number of characters \(1\), denoted as \(cnt\). If \(cnt\) cannot be divided by \(3\), then it is impossible to split the string, so we directly return \(0\). If \(cnt\) is \(0\), it means there are no characters \(1\) in the string. We can choose any two positions out of \(n-1\) positions to split the string into three substrings, so the number of ways is \(C_{n-1}^2\).

If \(cnt \gt 0\), we update \(cnt\) to \(\frac{cnt}{3}\), which is the number of characters \(1\) in each substring.

Next, we find the minimum index of the right boundary of the first substring, denoted as \(i_1\), and the maximum index of the right boundary of the first substring (exclusive), denoted as \(i_2\). Similarly, we find the minimum index of the right boundary of the second substring, denoted as \(j_1\), and the maximum index of the right boundary of the second substring (exclusive), denoted as \(j_2\). Then the number of ways is \((i_2 - i_1) \times (j_2 - j_1)\).

Note that the answer may be very large, so we need to take the modulo \(10^9+7\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the string \(s\).

Similar problems:

927. Three Equal Parts

Python3JavaC++Go

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)

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) 1e9 + 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;
            }
        }
    }
}

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;
    }
};

func numWays(s string) int {
    cnt := 0
    for _, c := range s {
        if c == '1' {
            cnt++
        }
    }
    m := cnt % 3
    if m != 0 {
        return 0
    }
    const mod = 1e9 + 7
    n := len(s)
    if cnt == 0 {
        return (n - 1) * (n - 2) / 2 % mod
    }
    cnt /= 3
    find := func(x int) int {
        t := 0
        for i := 0; ; i++ {
            if s[i] == '1' {
                t++
                if t == x {
                    return i
                }
            }
        }
    }
    i1, i2 := find(cnt), find(cnt+1)
    j1, j2 := find(cnt*2), find(cnt*2+1)
    return (i2 - i1) * (j2 - j1) % mod
}

1573. Number of Ways to Split a String

Description

Solutions

Solution 1: Counting

Comments