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

Problem Summary #

Given a binary string s  (a string containing only 0 and 1), we can split s into 3 non-empty strings s1, s2, s3 (s1 + s2 + s3 = s). Return the number of ways to split s such that the number of characters ‘1’ in s1, s2, and s3 is the same. Since the answer may be very large, return it modulo 10^9 + 7.

Solution Ideas #

• This problem tests knowledge of permutations and combinations. According to the problem statement, if the number of 1s is not a multiple of 3, return -1 directly. If there is no 1 in the string, then the number of splitting schemes is a combination: choose 2 positions among n-1 letters. Using the formula for combinations, the number of combinations is (n-1) * (n-2) / 2.
• The remaining case is when the number of 1s is a multiple of 3. Choose 2 positions in the string to divide it into 3 parts. Let the number of 0s between the last 1 of the first part and the first 1 of the second part be m1, and let the number of 0s between the last 1 of the second part and the first 1 of the third part be m2. By the multiplication principle, the number of schemes is m1 * m2.

Code #

package leetcode

func numWays(s string) int {
	ones := 0
	for _, c := range s {
		if c == '1' {
			ones++
		}
	}
	if ones%3 != 0 {
		return 0
	}
	if ones == 0 {
		return (len(s) - 1) * (len(s) - 2) / 2 % 1000000007
	}
	N, a, b, c, d, count := ones/3, 0, 0, 0, 0, 0
	for i, letter := range s {
		if letter == '0' {
			continue
		}
		if letter == '1' {
			count++
		}
		if count == N {
			a = i
		}
		if count == N+1 {
			b = i
		}
		if count == 2*N {
			c = i
		}
		if count == 2*N+1 {
			d = i
		}
	}
	return (b - a) * (d - c) % 1000000007
}