#1573

Medium

LeetCode Problem Workspace

Number of Ways to Split a String

Count the number of ways to split a binary string into three non-empty parts with equal numbers of '1's.

Problem Statement

Given a binary string s, split it into three non-empty parts s1, s2, and s3 such that s1 + s2 + s3 = s. The goal is to return the number of valid ways to perform the split such that the number of '1's in each part is equal.

If the sum of '1's in the entire string is not divisible by 3, no such split is possible. You should return the result modulo $10^9 + 7$ as the answer could be large.

Examples

Example 1

Input: s = "10101"

Output: 4

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 details omitted.

Example 3

Input: s = "0000"

Output: 3

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

Solution Approach

Check Divisibility by 3

First, check if the total count of '1's in the string is divisible by 3. If not, return 0 immediately as it's impossible to split the string in the required way.

Locate Positions of '1's

Identify the positions of all '1's in the string. Then, determine the target count of '1's per part. The positions can help in finding where to split the string into valid parts with equal '1's.

Calculate Possible Splits

Once we have the positions, calculate how many valid splits can occur by considering the possible ways to divide the positions of '1's into three groups. The answer is determined by the number of valid combinations of these splits.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity mainly depends on identifying the positions of '1's in the string, which takes $O(n)$ time, where $n$ is the length of the string. Finding the splits also takes linear time in the worst case, making the overall complexity $O(n)$ for time. Space complexity is $O(n)$ for storing the positions of '1's in the string.

What Interviewers Usually Probe

Candidate shows an understanding of the need to first check divisibility by 3.
Candidate knows how to identify the positions of '1's efficiently.
Candidate considers how to count valid splits based on the positions of '1's.

Common Pitfalls or Variants

Common pitfalls

Ignoring the requirement that the total number of '1's must be divisible by 3.
Failing to account for strings that contain no '1's or have fewer than three '1's.
Incorrectly calculating the number of valid splits by not considering all the possible ways to split the string.

Follow-up variants

What if the string contains only '0's?
How would you approach the problem if the string could contain other characters besides '0' and '1'?
What optimizations can be made if we are allowed to split the string into more than three parts?

FAQ

How do I approach the problem of splitting a binary string into three parts?

Start by checking if the total number of '1's in the string is divisible by 3. Then, calculate the positions of '1's and figure out how to split them into three parts with equal '1's.

What should I do if the sum of '1's is not divisible by 3?

If the total number of '1's is not divisible by 3, immediately return 0 because a valid split is not possible.

Why do I need to store the positions of '1's?

Storing the positions of '1's allows you to efficiently find where to split the string into three parts with equal numbers of '1's.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string. This is due to the need to check the positions of all '1's and calculate possible splits.

Can this problem be solved with dynamic programming?

Dynamic programming is not necessary for this problem as it can be solved efficiently with a linear scan of the string and careful counting of valid splits.

terminal

Solution

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

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)

Continue Practicing

#1513 number of substrings with only 1s #1447 simplified fractions #1759 count number of homogenous substrings