Skip to content

1573. Number of Ways to Split a String

SourceBiweekly Contest 34 Q2DifficultyMediumRating1590

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.

 

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

Solutions

Solution 1: Counting

Thinking

Split the string into three pieces with equally many ones. \(n\le 10^5\), so we cannot try every pair of cuts. Each piece must contain exactly one third of the ones.

If the total is not divisible by three there is no split; if there is no one at all, any two cuts work and the count is \(C_{n-1}^{2}\). Otherwise the first cut may sit anywhere between the \(\textit{cnt}\)-th and \((\textit{cnt}+1)\)-th one, and the second cut between the \(2\textit{cnt}\)-th and \((2\textit{cnt}+1)\)-th. The product of those two gap lengths is the answer.

First, we traverse the string \(s\) and count the number of characters \(1\), denoted as \(\textit{cnt}\). If \(\textit{cnt}\) cannot be divided by \(3\), then it is impossible to split the string, so we directly return \(0\). If \(\textit{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 \(\textit{cnt} \gt 0\), we update \(\textit{cnt}\) to \(\frac{\textit{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)\), where \(n\) is the length of the string \(s\).

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
}

Comments