1573. Number of Ways to Split a String

Problem

Given a binary string s (a string consisting only of '0's and '1's), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters '1' is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 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"

Example 4:

Input: s = "100100010100110"
Output: 12

Constraints:

• 3 <= s.length <= 10^5
• s[i] is '0' or '1'.

Discussion

The problem requires to find way of splitting a string with only 0s and 1s, where the string is split into three parts, and each part carrying equal numbers of 1s.

First we can come up with a brutal force solution, wheres we calculate all combinations of splitting the string with two moving pointers. Wheres should result in time complexity of O(n ^ 2). But we shall be able to optimize the problem into O(n).

We can consider the cases of input string and observe of solving patterns.

1. No. of 1s is zero
2. No. of 1s is not divisible by 3
3. No. of 1s is divisible by 3

For case 1, we can see all splitting way fulfills the requirements, so we return the numbers of way splitting the string into 3 parts, which equals to (n - 1) * (n - 2) / 2 (Consider two pointer as splitting position moving along all space between the characters).

For case 2, we can straightly return 0 as there is no correct ways to split.

For case 3, we can see the result equals to the combination of way of splitting between the first and second group of 1s and way of splitting between the second and third group of 1s

Hence, we can see that by saving all the index of 1s in the string, we can handle all the above three cases in a linear processing time.

Solution

Our solution begins with saving the index of 1s in the string to a list.

We then can further handle the three cases by counting the length of the list, which referring to the number of 1s in the string.

For case 1 and 2 the implementation is straight forward. For case 3, we first evaluate the chunk size of the 1 group, then we can find the starting and ending index of each 1 group. Hence the position of the 0s between the 1s groups are located.

Finally we evaluate the mod when returning the value.

class Solution:
    def numWays(self, s: str) -> int:
        index, size = [], len(s)

        for i in range(size):
            if s[i] == '1':
                index.append(i)

        count = len(index)
        if count == 0:
            result = (size - 1) * (size - 2) // 2

        elif count % 3 != 0:
            result = 0

        else:
            count = count // 3

            l = index[count] - index[count - 1]
            r = index[2 * count] - index[2 * count - 1]
            result = l * r

        return result % (10**9 + 7)

Complexity Analysis

• Time Complexity: O(n), as one iteration on the input string is required.
• Space Complexity: O(n), index of 1s is saved in memory, which is limited by the input size.