Jobs

Interviews

Discussions

Number of Ways to Split a String

#355 Most AskedMedium

Number of Ways to Split a String #355 Most Asked

Medium

Microsoft

3 views

Topics:

ArraysStringsTwo Pointers

Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s.

Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 10⁹ + 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"

Constraints:

3 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Try coding it in LeetCode

Number of Ways to Split a String

#355 Most AskedMedium

Number of Ways to Split a String #355 Most Asked

Medium

Microsoft

3 views

Topics:

ArraysStringsTwo Pointers

Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s.

Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 10⁹ + 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"

Constraints:

3 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string s?
What should I return if the input string `s` does not contain any '1's?
Should I assume the input string `s` will only contain '0' and '1' characters, or do I need to handle other characters?
By 'substring,' do you mean a contiguous sequence of characters from the original string?
If there are multiple valid ways to split the string, do you want me to return the total count of such ways?

Brute Force Solution

Approach

The brute force approach to splitting a string explores every conceivable way to divide it into three parts. We try every possible combination of splits, without any clever shortcuts, to see if the resulting parts meet the specified criteria. It's like exhaustively trying every possibility until we find all the valid ones.

Here's how the algorithm would work step-by-step:

First, imagine all the possible places you could cut the string to create the first part.
For each of those possible first parts, consider all the possible places you could cut the remainder of the string to create the second part.
The rest of the string then automatically becomes the third part.
For each of these combinations of three parts, check if they all meet a certain requirement (in this case, do all three parts have the same number of a particular character?).
If the parts do meet the requirement, then count that split as a valid way to split the string.
After considering all possible ways to cut the string into three parts, report the total number of valid ways we found.

Code Implementation

def number_of_ways_to_split_string_brute_force(input_string, target_character):
    number_of_valid_ways = 0
    string_length = len(input_string)

    for first_split_index in range(1, string_length - 1):
        for second_split_index in range(first_split_index + 1, string_length):
            first_substring = input_string[:first_split_index]
            second_substring = input_string[first_split_index:second_split_index]
            third_substring = input_string[second_split_index:]

            # Count the occurrences of the target char in each substring
            first_substring_target_count = first_substring.count(target_character)

            second_substring_target_count = second_substring.count(target_character)

            third_substring_target_count = third_substring.count(target_character)

            # Check if the counts are equal in all three substrings.
            if (
                first_substring_target_count
                == second_substring_target_count
                == third_substring_target_count
            ):
                # Increment the count of valid splits.
                number_of_valid_ways += 1

    return number_of_valid_ways

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach considers all possible splits of the string into three parts. The outer loop iterates through all possible ending positions for the first part, which takes O(n) time. For each of these first part choices, the inner loop iterates through all possible ending positions for the second part from the remaining string, which also takes O(n) time in the worst case. Therefore, the algorithm performs approximately n * n operations. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The brute force approach described iterates through all possible split locations using nested loops. It does not create any auxiliary data structures like lists, arrays, or hash maps to store intermediate results or visited states. The only extra space used is for a few integer variables to keep track of split indices and potentially a counter for valid splits, which remains constant regardless of the input string's size N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The key idea is to count the number of '1's in the string. If the total count isn't divisible by three, there are no valid splits. Otherwise, we find the positions where the cumulative count of '1's equals one-third and two-thirds of the total, and use these positions to calculate the possible splits.

Here's how the algorithm would work step-by-step:

First, count the total number of '1's in the entire string.
If this total isn't perfectly divisible by 3, there's no way to split the string correctly, so the answer is zero.
If the total number of '1's is zero, the answer is based on how many different ways you can split the string into three parts.
If the count of '1's is divisible by 3 and not zero, find the positions in the string where you reach one-third of the total '1's and where you reach two-thirds of the total '1's.
Count how many places you can make the first cut around the one-third position.
Count how many places you can make the second cut around the two-thirds position.
Multiply these two counts together to get the total number of valid splits.

Code Implementation

def number_of_ways_to_split_string(input_string):
    total_ones = input_string.count('1')

    # If the total number of ones isn't divisible by 3, return 0
    if total_ones % 3 != 0:
        return 0

    if total_ones == 0:
        string_length = len(input_string)
        return (string_length - 1) * (string_length - 2) // 2

    ones_per_part = total_ones // 3
    first_partition_ways = 0
    second_partition_ways = 0
    current_ones = 0

    # Count the number of valid first partitions.
    for i in range(len(input_string)):
        if input_string[i] == '1':
            current_ones += 1
        if current_ones == ones_per_part:
            first_partition_ways += 1

            # Need to break after finding valid first partition
            break

    current_ones = 0

    # Count valid second partitions after the first
    for i in range(len(input_string) - 1, -1, -1):
        if input_string[i] == '1':
            current_ones += 1
        if current_ones == ones_per_part:
            second_partition_ways += 1

            # Need to break after finding valid second partition
            break

    # Return the product of the valid first and second partitions.
    return first_partition_ways * second_partition_ways

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string once to count the total number of '1's. Then, depending on the count, it iterates through the string again at most twice: once to find the positions for the one-third count and once for the two-thirds count. Since the number of iterations is proportional to the length of the string (n) in the worst case, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm primarily uses a few integer variables to store counts and indices like the total count of '1's, the counts for one-third and two-thirds, and possibly indices for the positions where these counts are reached. These variables occupy constant space, irrespective of the input string's length. No auxiliary data structures such as lists or hashmaps are created. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty string or null input	Return 0 immediately, as there are no splits possible.
String with no ones	Return (n-1)*(n-2)/2, where n is the length of the string, since any split is valid.
String with a number of ones not divisible by 3	Return 0, as it's impossible to split into three equal parts of ones.
String with only one '1'	Return 0 because we require each of the three parts to have the same, and therefore more than 0, number of 1s.
String with only two '1's	Return 0 because we require each of the three parts to have the same, and therefore more than 0, number of 1s.
String with a very large number of zeros between significant '1's, potentially leading to integer overflow in intermediate calculations	Use long long to store the number of ways to split each group to prevent overflow.
Very long string with many possible solutions - check for time complexity efficiency	Ensure the algorithm iterates through the string only a constant number of times to avoid exceeding time limits.
String where the ones are clustered near the beginning or end	The counting of valid split points needs to correctly handle cases where groups of ones are located at the beginning or the end.

Empty string or null input

How to Handle:

Return 0 immediately, as there are no splits possible.

String with no ones

How to Handle:

Return (n-1)*(n-2)/2, where n is the length of the string, since any split is valid.

String with a number of ones not divisible by 3

How to Handle:

Return 0, as it's impossible to split into three equal parts of ones.

String with only one '1'

How to Handle:

Return 0 because we require each of the three parts to have the same, and therefore more than 0, number of 1s.

String with only two '1's

How to Handle:

Return 0 because we require each of the three parts to have the same, and therefore more than 0, number of 1s.

String with a very large number of zeros between significant '1's, potentially leading to integer overflow in intermediate calculations

How to Handle:

Use long long to store the number of ways to split each group to prevent overflow.

Very long string with many possible solutions - check for time complexity efficiency

How to Handle:

Ensure the algorithm iterates through the string only a constant number of times to avoid exceeding time limits.

String where the ones are clustered near the beginning or end

How to Handle:

The counting of valid split points needs to correctly handle cases where groups of ones are located at the beginning or the end.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string s?
What should I return if the input string `s` does not contain any '1's?
Should I assume the input string `s` will only contain '0' and '1' characters, or do I need to handle other characters?
By 'substring,' do you mean a contiguous sequence of characters from the original string?
If there are multiple valid ways to split the string, do you want me to return the total count of such ways?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine all the possible places you could cut the string to create the first part.
For each of those possible first parts, consider all the possible places you could cut the remainder of the string to create the second part.
The rest of the string then automatically becomes the third part.
For each of these combinations of three parts, check if they all meet a certain requirement (in this case, do all three parts have the same number of a particular character?).
If the parts do meet the requirement, then count that split as a valid way to split the string.
After considering all possible ways to cut the string into three parts, report the total number of valid ways we found.

Code Implementation

def number_of_ways_to_split_string_brute_force(input_string, target_character):
    number_of_valid_ways = 0
    string_length = len(input_string)

    for first_split_index in range(1, string_length - 1):
        for second_split_index in range(first_split_index + 1, string_length):
            first_substring = input_string[:first_split_index]
            second_substring = input_string[first_split_index:second_split_index]
            third_substring = input_string[second_split_index:]

            # Count the occurrences of the target char in each substring
            first_substring_target_count = first_substring.count(target_character)

            second_substring_target_count = second_substring.count(target_character)

            third_substring_target_count = third_substring.count(target_character)

            # Check if the counts are equal in all three substrings.
            if (
                first_substring_target_count
                == second_substring_target_count
                == third_substring_target_count
            ):
                # Increment the count of valid splits.
                number_of_valid_ways += 1

    return number_of_valid_ways

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count the total number of '1's in the entire string.
If this total isn't perfectly divisible by 3, there's no way to split the string correctly, so the answer is zero.
If the total number of '1's is zero, the answer is based on how many different ways you can split the string into three parts.
If the count of '1's is divisible by 3 and not zero, find the positions in the string where you reach one-third of the total '1's and where you reach two-thirds of the total '1's.
Count how many places you can make the first cut around the one-third position.
Count how many places you can make the second cut around the two-thirds position.
Multiply these two counts together to get the total number of valid splits.

Code Implementation

def number_of_ways_to_split_string(input_string):
    total_ones = input_string.count('1')

    # If the total number of ones isn't divisible by 3, return 0
    if total_ones % 3 != 0:
        return 0

    if total_ones == 0:
        string_length = len(input_string)
        return (string_length - 1) * (string_length - 2) // 2

    ones_per_part = total_ones // 3
    first_partition_ways = 0
    second_partition_ways = 0
    current_ones = 0

    # Count the number of valid first partitions.
    for i in range(len(input_string)):
        if input_string[i] == '1':
            current_ones += 1
        if current_ones == ones_per_part:
            first_partition_ways += 1

            # Need to break after finding valid first partition
            break

    current_ones = 0

    # Count valid second partitions after the first
    for i in range(len(input_string) - 1, -1, -1):
        if input_string[i] == '1':
            current_ones += 1
        if current_ones == ones_per_part:
            second_partition_ways += 1

            # Need to break after finding valid second partition
            break

    # Return the product of the valid first and second partitions.
    return first_partition_ways * second_partition_ways

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string or null input	Return 0 immediately, as there are no splits possible.
String with no ones	Return (n-1)*(n-2)/2, where n is the length of the string, since any split is valid.
String with a number of ones not divisible by 3	Return 0, as it's impossible to split into three equal parts of ones.
String with only one '1'	Return 0 because we require each of the three parts to have the same, and therefore more than 0, number of 1s.
String with only two '1's	Return 0 because we require each of the three parts to have the same, and therefore more than 0, number of 1s.
String with a very large number of zeros between significant '1's, potentially leading to integer overflow in intermediate calculations	Use long long to store the number of ways to split each group to prevent overflow.
Very long string with many possible solutions - check for time complexity efficiency	Ensure the algorithm iterates through the string only a constant number of times to avoid exceeding time limits.
String where the ones are clustered near the beginning or end	The counting of valid split points needs to correctly handle cases where groups of ones are located at the beginning or the end.

Empty string or null input

How to Handle:

Return 0 immediately, as there are no splits possible.

String with no ones

How to Handle:

Return (n-1)*(n-2)/2, where n is the length of the string, since any split is valid.

String with a number of ones not divisible by 3

How to Handle:

Return 0, as it's impossible to split into three equal parts of ones.

String with only one '1'

How to Handle:

Return 0 because we require each of the three parts to have the same, and therefore more than 0, number of 1s.

String with only two '1's

How to Handle:

Return 0 because we require each of the three parts to have the same, and therefore more than 0, number of 1s.

String with a very large number of zeros between significant '1's, potentially leading to integer overflow in intermediate calculations

How to Handle:

Use long long to store the number of ways to split each group to prevent overflow.

Very long string with many possible solutions - check for time complexity efficiency

How to Handle:

Ensure the algorithm iterates through the string only a constant number of times to avoid exceeding time limits.

String where the ones are clustered near the beginning or end

How to Handle:

The counting of valid split points needs to correctly handle cases where groups of ones are located at the beginning or the end.

0/1114 Microsoft questions completed

0/1114 completed