1573. Number of Ways to Split a String

MediumMathString
Leetcode Link

Problem Description

The problem involves a binary string s, which consists only of '0's and '1's. The task is to find out how many different ways we can split this string into three non-empty substrings (s1, s2, and s3) such that the number of '1's is the same in each substring. If this condition cannot be met, we should return 0. If there are multiple ways to split the string that satisfy the condition, we should return the total count of such possibilities. Since the number of ways can be very large, it is only required to return the result modulo 10^9 + 7.

Here's a more detailed explanation:

  • If s is split into s1, s2, and s3, then s1 + s2 + s3 = s, which means they are consecutive parts of the original string.
  • All three parts must have the same number of '1's, which also implies that the total number of '1's in s must be divisible by 3.
  • If s doesn't contain any '1's, any split that partitions s into three parts would satisfy the condition since each part will have zero '1's.
  • If the total number of '1's in s isn't divisible by 3, there is no way to split s to satisfy the given condition, so the result is 0.

Intuition

The solution is built on the understanding that to split the string into three parts with an equal number of '1's, the number of '1's must be divisible by 3.

  • We start by counting the total number of '1's in the string. If the count is not divisible by 3, we can immediately return 0, since it's impossible to divide the '1's equally into three parts.
  • If there are no '1's, then the binary string consists only of '0's. The string can then be split in any place between the '0's. The number of ways to choose two split points in a string of length n is (n-1)*(n-2)/2.
  • If there are '1's in the string, we need to find the split points that give us the correct distribution of '1's. To do this, the following steps are taken:
    • We find the indices of the first and second occurrences of the cnt-th '1' (where cnt is the total number of '1's divided by 3), as well as the indices for the first and second occurrences of the 2*cnt-th '1'.
    • These indices help us identify the positions at which we can make our splits.
    • The number of ways to make the first split is the difference between the second and first occurrences of the cnt-th '1'.
    • The number of ways to make the second split is similarly the difference between the second and first occurrences of the 2*cnt-th '1'.
    • Multiplying these two numbers gives us the total number of ways to split the string to ensure all three parts have the same number of '1's.

The modulus operation is used to ensure the result stays within numerical bounds as per the problem's instructions.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

In the given solution, the algorithm begins with some pre-processing to calculate the total number of '1's present in the input string s. This uses the sum function and a generator expression to count '1's, sum(c == '1' for c in s). The result is then divided by 3 with the divmod function, which returns a tuple containing the quotient and the remainder.

  • If the remainder is not zero, it indicates that it's impossible to distribute '1's equally into three parts, and the function immediately returns 0.
  • If the quotient is zero (i.e., no '1's in the string), the solution uses the combination formula to calculate the number of ways to choose two positions out of n-1 possible positions as split points. This is done using the formula ((n - 1) * (n - 2) // 2) % mod, where n is the length of the string and mod is the required modulus 10^9 + 7.

Next, the solution involves finding the exact points to split the string when '1's exist. For this purpose, the find function is defined, which iterates over the string and counts '1's until it reaches a target number (for example, the cnt-th '1' or 2*cnt-th '1'). It returns the index where this occurs.

  • The find function is used four times to find two pairs of indices: i1, i2, which are the indices before and after the last '1' in the first third of '1's, and j1, j2, the corresponding indices for the second third of '1's.
  • i1 is obtained by looking for the cnt-th '1', while i2 is obtained by searching for the occurrence of one more '1' after i1 (i.e., cnt + 1). Similarly, j1 is the index of the 2*cnt-th '1' and j2 for one more '1' after j1 (i.e., 2*cnt + 1).
  • These indices mark the possible split points just before and after the identified '1's.

Once the split points are determined, the total number of ways to split s is the product of the number of ways to split at each pair of indices i and j, effectively (i2 - i1) * (j2 - j1). The product is taken modulo mod to avoid large numbers and comply with the problem's requirement to output the result modulo 10^9 + 7.

The solution effectively leverages basic counting principles and a single pass through the string to accomplish the task, ensuring a linear time complexity proportionate to the length of the string s. It uses very few additional data structures outside of basic counters and indices.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's consider a small example to illustrate the solution approach with a binary string s = "0011001".

  1. First, we count the total number of '1's in the string s. There are 3 ones in 0011001.
  2. We check if the total number of '1's is divisible by 3. Since 3 is divisible by 3, we can proceed.
  3. We need to find the partition points in the string such that each partition contains exactly one '1'.
  4. We start scanning the string to find the 1st '1', which is the cnt-th '1' (in our case, 1 as 3/3=1), and we find it at index 2.
  5. We continue scanning to find the occurrence of the next '1' after the cnt-th '1', which is at index 3. This gives us our first potential split between indices 2 and 3.
  6. We repeat the process for finding the 2*cnt-th '1' and the first occurrence after that. We find the next '1' at index 4 and the one after that at index 6.
  7. These indices give us the second potential split between indices 4 and 6.

Now, let's calculate how many ways we can split s at these points:

  • The first split can occur at either index 2 or 3, so 2 ways (i2 - i1 where i1 = 2 and i2 = 3).
  • The second split can occur at either index 4 or 6, so 3 ways (j2 - j1 where j1 = 4 and j2 = 6).

To find the total number of ways to split the string to ensure all three parts have the same number of '1's, we multiply the number of ways for each split.

  • This gives us 2 * 3 = 6 ways to split the string 0011001 into three parts, each containing the same number of '1's.

The result we obtained is the direct application of the algorithm described in the solution. The modulus operation is not necessary in this example because our final count is already within the bounds of 10^9 + 7. However, in a solution implementation, the count would be taken modulo 10^9 + 7 as specified.

Solution Implementation

1class Solution:
2    def numWays(self, s: str) -> int:
3        def find_nth_occurrence(x):
4            """Find the index of the nth occurrence of '1' in the string."""
5            total_ones = 0
6            # Enumerate over string characters and count ones
7            for index, char in enumerate(s):
8                total_ones += int(char == '1')
9                # When the nth occurrence is reached, return the index
10                if total_ones == x:
11                    return index
12            return None  # If the nth occurrence doesn't exist
13      
14        # Count the total number of '1's in the string and check if it can be divided into 3 parts
15        ones_count, remainder = divmod(sum(char == '1' for char in s), 3)
16      
17        # If it's not divisible by 3, there are no ways to split, return 0
18        if remainder:
19            return 0
20      
21        n = len(s)  # Length of the input string
22        # A modulus constant for the result as per LeetCode's requirement
23        mod = 10**9 + 7  
24      
25        # When there are no '1's, we can choose 2 points to split the '0's into 3 parts
26        if ones_count == 0:
27            # Computing combination n-1 choose 2
28            return ((n - 1) * (n - 2) // 2) % mod
29      
30        # Find the indices for splitting
31        # The first split is after the 'ones_count'th '1'
32        first_split_index_start = find_nth_occurrence(ones_count)
33        # The second split is after the first '1' that follows the first split
34        first_split_index_end = find_nth_occurrence(ones_count + 1)
35      
36        # Similarly for the second split
37        second_split_index_start = find_nth_occurrence(ones_count * 2)
38        second_split_index_end = find_nth_occurrence(ones_count * 2 + 1)
39      
40        # Calculate the number of ways to split for the first and second split
41        # Multiply them and return the result modulo 10^9 + 7
42        return (first_split_index_end - first_split_index_start) * (second_split_index_end - second_split_index_start) % mod
43
44# Example usage:
45sol = Solution()
46result = sol.numWays("10101")  # Should return 4 as there are four ways to split "10101" into three parts with equal number of '1's.
47print(result)  # Output: 4
48
1class Solution {
2    private String binaryString; // Renamed s to binaryString for clarity
3
4    // Method to count the number of ways to split the given string in three parts with an equal number of '1's
5    public int numWays(String binaryString) {
6        this.binaryString = binaryString; // Initializing the class-level variable
7        int onesCount = 0; // Counter for the number of '1's in the string
8        int stringLength = binaryString.length(); // Store the length of the string
9
10        // Count the number of '1's in the string
11        for (int i = 0; i < stringLength; ++i) {
12            if (binaryString.charAt(i) == '1') {
13                ++onesCount;
14            }
15        }
16
17        int remainder = onesCount % 3; // Calculate remainder to check if onesCount is divisible by 3
18        if (remainder != 0) {
19            // If not divisible by three, return 0 as it's impossible to split the string properly
20            return 0;
21        }
22        final int mod = (int) 1e9 + 7; // Modulus value for the result
23      
24        // If the string contains no '1's, calculate the number of ways to split the zeros
25        if (onesCount == 0) {
26            // Number of subarrays is a combination: Choose 2 from stringLength - 1 and take mod
27            return (int) (((stringLength - 1L) * (stringLength - 2) / 2) % mod);
28        }
29
30        onesCount /= 3; // Divide the count of '1's by 3 to find the size of each part
31        // Find positions around the first third
32        long firstCutStart = findCutPosition(onesCount);
33        long firstCutEnd = findCutPosition(onesCount + 1);
34        // Find positions around the second third
35        long secondCutStart = findCutPosition(onesCount * 2);
36        long secondCutEnd = findCutPosition(onesCount * 2 + 1);
37        // Calculate the number of ways to make the cuts and take mod
38        return (int) ((firstCutEnd - firstCutStart) * (secondCutEnd - secondCutStart) % mod);
39    }
40
41    // Helper method to find the cut positions in the binary string
42    private int findCutPosition(int targetOnesCount) {
43        int tempCounter = 0; // Temporary counter to track the number of '1's
44        // Look for the position in the string that corresponds to the target count of '1's
45        for (int i = 0;; ++i) {
46            tempCounter += binaryString.charAt(i) == '1' ? 1 : 0;
47            if (tempCounter == targetOnesCount) {
48                // Once found, return the index of the string at that count
49                return i;
50            }
51        }
52    }
53}
54
1class Solution {
2public:
3    int numWays(string s) {
4        // Count the number of '1's in the string.
5        int oneCount = 0;
6        for (char c : s) {
7            oneCount += (c == '1');
8        }
9      
10        // If oneCount is not divisible by 3, there's no way to split.
11        if (oneCount % 3 != 0) {
12            return 0;
13        }
14      
15        // Define modulo for the result as required by the problem.
16        const int MOD = 1e9 + 7;
17        int length = s.size();
18
19        // If there are no '1's in the string, return the number of ways to choose
20        // the points to split the string in 3 parts, avoiding permutations.
21        if (oneCount == 0) {
22            return ((long long)(length - 1) * (long long)(length - 2) / 2) % MOD;
23        }
24      
25        // Adjust oneCount to be one third of the original oneCount
26        oneCount /= 3;
27
28        // Helper lambda function to find the index of the start of a particular group of '1's.
29        auto findIndexOfGroupStart = [&](int groupCount) -> int {
30            int count = 0;
31            for (int i = 0; ; ++i) {
32                count += (s[i] == '1');
33                if (count == groupCount) {
34                    return i;
35                }
36            }
37        };
38      
39        // Find the indices where the first and second splits should occur.
40        int firstSplitStart = findIndexOfGroupStart(oneCount);
41        int firstSplitEnd = findIndexOfGroupStart(oneCount + 1);
42        int secondSplitStart = findIndexOfGroupStart(oneCount * 2);
43        int secondSplitEnd = findIndexOfGroupStart(oneCount * 2 + 1);
44
45        // Calculate the number of ways to make the splits and return the result module MOD.
46        return ((long long)(firstSplitEnd - firstSplitStart) * (long long)(secondSplitEnd - secondSplitStart)) % MOD;
47    }
48};
49
1// Global variable to define modulo for the result as required by the problem
2const MOD: number = 1e9 + 7;
3
4// Function to count the number of '1's in the string
5function countOnes(s: string): number {
6    let oneCount = 0;
7    for (let c of s) {
8        oneCount += (c === '1') ? 1 : 0;
9    }
10    return oneCount;
11}
12
13// Function to find the index of the start of a particular group of '1's
14function findIndexOfGroupStart(s: string, groupCount: number): number {
15    let count = 0;
16    for (let i = 0; i < s.length; i++) {
17        if (s[i] === '1') count++;
18        if (count === groupCount) {
19            return i;
20        }
21    }
22    return -1; // This condition should not happen due to input constraints
23}
24
25// Function that calculates the number of ways the input string s can be split into three parts with equal number of '1's
26function numWays(s: string): number {
27    let oneCount = countOnes(s);
28    let length = s.length;
29
30    // If oneCount is not divisible by 3, there's no way to split the string
31    if (oneCount % 3 !== 0) {
32        return 0;
33    }
34
35    // If there are no '1's in the string, return the number of ways to choose
36    // the points to split the string in 3 parts, avoiding permutations.
37    if (oneCount === 0) {
38        // Using modular arithmetic for calculating binomial coefficient (n - 1) choose 2
39        return (((length - 1) * (length - 2) / 2) % MOD);
40    }
41
42    // Adjust oneCount to be one third of the original oneCount
43    oneCount /= 3;
44
45    // Find the indices where the first and second splits should occur
46    let firstSplitStart = findIndexOfGroupStart(s, oneCount);
47    let firstSplitEnd = findIndexOfGroupStart(s, oneCount + 1);
48    let secondSplitStart = findIndexOfGroupStart(s, oneCount * 2);
49    let secondSplitEnd = findIndexOfGroupStart(s, oneCount * 2 + 1);
50
51    // Calculate the number of ways to make the first and the second split.
52    // Multiply the number of zeroes between the adjacent groups of '1', and take the result module MOD
53    return ((firstSplitEnd - firstSplitStart) * (secondSplitEnd - secondSplitStart)) % MOD;
54}
55
56// Example usage:
57// const s: string = "10101";
58// console.log(numWays(s)); // The output would be 4
59
Not Sure What to Study? Take the 2-min Quiz：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Time and Space Complexity

Time Complexity

The given code snippet includes three significant calculations: counting the number of 1's in the string, finding the indices where certain counts of 1's occur, and calculating the total number of ways to split the string.

  1. Counting the number of 1's: This is done by iterating over each character in the string once. This operation takes O(n) time where n is the length of the string s.

  2. Finding the indices with the help of the find function: This function is called four times. Each call to the find method iterates over the entire string in the worst-case scenario, which makes it O(n) for each call. Therefore, for four calls, the time complexity associated with the find function is O(4 * n) which simplifies to O(n).

  3. Calculating combinations for zero counts of 1's: The calculation ((n - 1) * (n - 2) // 2) % mod is executed in constant time O(1), as it doesn't depend on the size of the input string beyond the length calculation.

Hence, the overall time complexity of the code is O(n) for scanning the string to count the number of 1's plus O(n) for the find operations, which simplifies to O(n).

Space Complexity

  1. cnt and m: These are constant-size integers, which occupy O(1) space.

  2. Counting 1's: The sum comprehension iterates over the string and counts the number of '1's, which does not require additional space, so it is O(1).

  3. Variables i1, i2, j1, j2, and n: They are also constant-size integers, with no additional space dependent on the input size, so this is O(1).

  4. The function find uses i and t which again are constant-size integers, hence O(1) space.

As there are no data structures used that scale with the size of the input, the overall space complexity of the code is O(1), which represents constant space usage.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫