Leetcode 1573. Number of Ways to Split a String

Problem Explanation:

The Problem is asking us to find the number of ways we can split a given binary string into exactly three non-empty substrings such that each part has the same number of '1'.

We are given a string that just contains binary digits either '0' or '1'. We have to split this string into three different substrings in a way that all three strings should have the same number of '1'. If it is not possible to split the string in the above-described way then return 0.

The complete logic of solving this problem is to find the number of ways to split the string into three substrings that have an equal number of '1' in each substring.

For example, suppose if we have string s ="100100010100110". The count of '1' in the string s is 6.

• We can adjust one '1' to each section,

• Count the number of ways that can form the first segment ending, and the third segment starting.

• Since it will be impossible to split the string into three equal parts if the count of 1s is not divisible by 3, in that case, we return 0.

• If the count of 1s is 0, then we have n-1 possible splits, we choose 2 out of them. That would be (n-1 choose 2).

Walkthrough of the above example:

If the number of 1's in string s is 6, to split them into three equal subset strings, we can distribute 2 '1's to each of the 3 strings s1, s2 and s3.

To find the indexes of how we can split the string into three equal substrings, let's walk through the string:

• For the first part (s1+s2), there can be several ways to end, say index a;

• For the third part (s2+s3), there can be several ways to start, say index b;

• For each a, if we find a b, where b>a, it's a way of splitting.

The total number of ways of splitting the string is to sum them up.

Let's consider the following string s = "100100010100110"

From the start, we encounter 1st '1' at string[0] (0-index based), 2nd '1' at string[2], 3rd '1' at string[3], 4th '1' at string[5], 5th '1' at string[7], 6th '1' at string[11]

If we count the number of '0' between 2nd '1' & 3rd '1' => s[3] - s[2] - 1 = 0, resulting in only 1 possible way to split between them

Similarly between 4th '1' & 5th '1' => s[7] - s[5] - 1 = 1, resulting in 2 possible ways to split between them

And between 5th '1' & 6th '1' => s[11] - s[7] - 1 = 3, resulting in 4 possible ways to split between them

Taking these factors into account for each split, the total possible ways to split the string would be 1 * 2 * 4 = 8

Final Explanation:

In the end, We just need to find the index and multiply the possible splits to eventually get the number of ways to split.

let's, s1 = string[0] to string[s1End], s2 = string[s2Start] to string[s2End], s3 = string[s3Start] to end of string

Then, simply multiple these two parts (s2Start - s1End) and (s3Start - s2End), we can get the answer.

Python Solution:

Here is an implementation in Python:

1
2python
3class Solution:
4    def numWays(self, s: str) -> int:
5        MOD = 10**9 + 7
6        ones = sum(c == '1' for c in s)
7        n = len(s)
8        if ones % 3 != 0:
9            return 0
10        elif ones == 0:
11            return (n-2)*(n-1)//2 % MOD
12        ones //= 3
13        l = r = c = 0
14        for i in range(n):
15            if s[i] == '1':
16                c += 1
17            if c == ones:
18                l += 1
19            elif c == 2*ones:
20                r += 1
21        return l * r % MOD

The time and space complexity of the solution is O(n), where n is the length of the given string.

C++ Solution:

Here is an implementation in C++:

1
2c++
3class Solution {
4public:
5    int numWays(string s) {
6        constexpr int kMod = 1'000'000'007; // Assigning the modulo value
7        const int ones = count(begin(s), end(s), '1'); // Counting number of ones in the string
8        if (ones % 3 != 0) // If no. of ones is not divisible by 3
9          return 0;  // Return 0 as string cant be split into 3 with equal 1s
10        if (ones == 0) {  // If there are no ones in the string
11          const long n = s.size();
12          return (n - 1) * (n - 2) / 2 % kMod; // Return total possible ways to split string
13        }
14
15        int s1End = -1;
16        int s2Start = -1;
17        int s2End = -1;
18        int s3Start = -1;
19        int onesSoFar = 0;
20
21        for (int i = 0; i < s.length(); ++i) {
22          if (s[i] == '1') 
23            ++onesSoFar;
24          if (s1End == -1 && onesSoFar == ones / 3)
25            s1End = i;
26          else if (s2Start == -1 && onesSoFar == ones / 3 + 1)
27            s2Start = i;
28          if (s2End == -1 && onesSoFar == ones / 3 * 2)
29            s2End = i;
30          else if (s3Start == -1 && onesSoFar == ones / 3 * 2 + 1)
31            s3Start = i;
32        }
33
34        return static_cast<long>(s2Start - s1End) * (s3Start - s2End) % kMod;
35    }
36};

Time and Space Complexity:

Time Complexity: The time complexity of the solution is O(n).

Space Complexity: The space complexity of the solution is O(1).

Java Solution:

Here is a solution in Java:

1
2java
3public class Solution {
4public int numWays(String s) {
5    final int MOD = 1_000_000_007; 
6    int ones = 0;
7    long ans = 0;
8    int n = s.length();
9    for (char c : s.toCharArray())
10        ones += c == '1' ? 1 : 0;
11    if (ones % 3 != 0) return 0;
12    else if (ones == 0)
13        return (int) ((n - 2L) * (n - 1L) / 2 % MOD);
14    ones /= 3;
15    long l = 0, r = 0;
16    int count = 0;
17    for (char c : s.toCharArray()) {
18        if (c == '1') count++;
19        if (count == ones) l++;
20        else if (count == ones * 2) r++;
21    }
22    
23    return (int) (l * r % MOD);
24  }
25}

The time and space complexity of the solution is O(n) and O(1), respectively. In this solution, l is the count of all possible end positions for the first part and r is the count of all possible start positions for the last part.

JavaScript Solution

Here is an implementation in JavaScript:

1
2javascript
3var numWays = function(s) {
4    let ones = 0;
5    let MOD = 10**9 + 7;
6    for (let i=0; i<s.length; i++){
7        if (s[i] == '1') ones++;
8    }
9    if (ones % 3 != 0) return 0;
10    if (ones == 0) {
11        return (BigInt(s.length - 1) * BigInt(s.length - 2) / BigInt(2)) % BigInt(MOD); 
12    }
13    
14    ones /= 3;
15    let p1 = 0, p2 = 0, count = 0;
16    
17    for (let i=0; i<s.length; i++){
18        if (s[i] == '1') count++;
19        if (count == ones) p1++;
20        if (count == 2*ones) p2++;
21    }
22    
23    return Number((BigInt(p1) * BigInt(p2)) % BigInt(MOD));
24};

This solution is also O(n) time complexity and O(1) space complexity. At the end of if condition s[i] == '1', p1 refers to the number of ways to end the first cut and p2 refers to the number of ways to start the last cut, so multiplying them gives the answer.

C# solution

Here is an implementation in C#:

1
2csharp
3public class Solution {
4    public int NumWays(string s) {
5        const int mod = 1_000_000_007, zero = 0;
6        int first = zero, second = zero, numOnes = zero;
7        foreach (char c in s) numOnes += c == '1' ? 1 : zero;
8        if (numOnes % 3 != zero) 
9            return zero;
10        else if (numOnes == zero)
11            return (int)(((long)(s.Length - 2) * (long)(s.Length - 1) / 2L) % mod);
12        numOnes /= 3;
13        int count = zero;
14        for (int i = 0; i < s.Length; i++) {
15            if (s[i] == '1') count++;
16            if (count == numOnes) first++;
17            else if (count == 2 * numOnes) second++;
18        }
19        return (int)((first * (long)second) % mod);
20    }
21}

The time and space complexity of the solution is O(n) and O(1), respectively. If the number of ones is not divisible by 3 then return zero, else find and return all possible combinations.

Ruby Solution

Here is an implementation in Ruby:

1
2ruby
3# @param {String} s
4# @return {int}
5def num_ways(s)
6    ones = s.count('1')
7    return 0 if ones % 3 != 0
8    len = s.length
9    return (len - 1) * (len - 2) / 2 % (10 ** 9 + 7) if ones == 0
10    ones /= 3
11    l, r, c = 0, 0, 0
12    s.each_char do |cur|
13        if cur == '1'
14            c += 1
15        end
16        if c == ones
17            l += 1
18        elsif c == 2 * ones
19            r += 1
20        end
21    end
22    return l * r % (10 ** 9 + 7)
23end

Each implementation simply counts the number of ways to make the first and last cut after dividing the total number of 1s by 3. We count up these possibilities for the first two segments and multiply for the total answer.

All solutions have a O(n) time complexity because they are all single-pass, and O(1) space complexity because they only use a fixed amount of space to store the variables. They are efficient and clean solutions for solving this problem.

Each piece of code solves the problem in a slightly different way, making use of the unique features of each language, but they all follow the same underlying strategy of counting ones and finding split points. The key point to keep in mind is that the number of ones has to be divisible by three for it to be possible to split the string into three parts with an equal number of ones. If this condition is not met, there's no possible way to do the split and the function should return zero. If the condition is met, the function should calculate the possible split points and return the count of these points.

Overall, these solutions provide a good demonstration of how to approach a problem like this in several different programming languages, and should provide a good starting point for learning more about string manipulation and combinatorics in your language of choice.