Jobs

Interviews

Discussions

Count the Number of Substrings With Dominant Ones

Medium

Amazon

2 views

Topics:

Strings

You are given a binary string s.

Return the number of substrings with dominant ones.

A string has dominant ones if the number of ones in the string is greater than or equal to the square of the number of zeros in the string.

Example 1:

s = "00011"

Output: 5

Explanation:

The substrings with dominant ones are shown in the table below.

i	j	s[i..j]	Number of Zeros	Number of Ones
3	3	1	0	1
4	4	1	0	1
2	3	01	1	1
3	4	11	0	2
2	4	011	1	2

Example 2:

s = "101101"

Output: 16

Explanation:

The substrings with non-dominant ones are shown in the table below.

Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.

i	j	s[i..j]	Number of Zeros	Number of Ones
1	1	0	1	0
4	4	0	1	0
1	4	0110	2	2
0	4	10110	2	3
1	5	01101	2	3

Constraints:

1 <= s.length <= 4 * 10^4
s consists only of characters '0' and '1'.

Count the Number of Substrings With Dominant Ones

Medium

Amazon

2 views

Topics:

Strings

You are given a binary string s.

Return the number of substrings with dominant ones.

A string has dominant ones if the number of ones in the string is greater than or equal to the square of the number of zeros in the string.

Example 1:

s = "00011"

Output: 5

Explanation:

The substrings with dominant ones are shown in the table below.

i	j	s[i..j]	Number of Zeros	Number of Ones
3	3	1	0	1
4	4	1	0	1
2	3	01	1	1
3	4	11	0	2
2	4	011	1	2

Example 2:

s = "101101"

Output: 16

Explanation:

The substrings with non-dominant ones are shown in the table below.

Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.

i	j	s[i..j]	Number of Zeros	Number of Ones
1	1	0	1	0
4	4	0	1	0
1	4	0110	2	2
0	4	10110	2	3
1	5	01101	2	3

Constraints:

1 <= s.length <= 4 * 10^4
s consists only of characters '0' and '1'.

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 possible length of the binary string?
If the input string is empty or null, what should I return?
By 'dominant ones,' do you mean that the number of ones in the substring must be strictly greater than the number of zeros, or is equality acceptable?
Are there any specific constraints on the characters allowed in the string, or is it guaranteed to only contain '0' and '1'?
Could you provide a small example to illustrate the expected behavior and output format?

Brute Force Solution

Approach

We want to find all sections within a sequence where there are more ones than zeros. The brute force way checks every single possible section to see if it meets the criteria.

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

First, consider every section that starts at the very beginning of the sequence.
Check if the first number alone has more ones than zeros. If so, count it.
Then, check the first two numbers together. If they have more ones than zeros, count that section too.
Continue adding one number at a time to the section, each time checking if the section has more ones than zeros, and counting it if it does.
Once you've checked all the sections that start at the beginning, move on and repeat the process starting from the second number in the sequence.
Keep doing this, moving one number at a time and starting a new set of section checks, until you reach the end of the sequence.
In the end, add up all the sections you counted that had more ones than zeros. This total number is the final answer.

Code Implementation

def count_substrings_with_dominant_ones(sequence):
    total_substrings_with_more_ones = 0

    for starting_index in range(len(sequence)):
        for ending_index in range(starting_index, len(sequence)):

            # Extract the current substring for evaluation.
            current_substring = sequence[starting_index:ending_index + 1]

            number_of_ones = 0
            number_of_zeros = 0

            for bit in current_substring:
                if bit == '1':
                    number_of_ones += 1
                else:
                    number_of_zeros += 1

            # Determine if the substring has more ones than zeros
            if number_of_ones > number_of_zeros:

                # Count substrings that satisfy the condition.
                total_substrings_with_more_ones += 1

    # Returns the final count
    return total_substrings_with_more_ones

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input sequence of size n, using a nested loop structure. The outer loop considers each element as a potential starting point for a substring. The inner loop extends the substring from that starting point to the end of the sequence, effectively checking all possible substrings. The number of substrings checked scales proportionally to n * (n+1) / 2. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The described brute force solution iterates through all possible substrings of the input sequence. It calculates the number of ones and zeros within each substring directly without using any additional data structures like arrays, lists, or hash maps to store intermediate results. The algorithm only uses a few constant space variables (e.g., counters for ones and zeros), regardless of the input sequence length N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The most efficient approach focuses on tracking groups of consecutive ones and leveraging that information to count valid substrings quickly. By avoiding redundant calculations, we can determine the number of substrings with more ones than zeros in a single pass.

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

First, go through the entire input string and identify all the consecutive groups of ones.
For each group of consecutive ones, determine its length.
Then, consider each group of consecutive ones as the *end* of a valid substring. We'll count how many substrings *ending* with that group are valid.
To do that, for each group, look to the left. How many characters to the left do you need to include in your substring so that the number of ones you have (from your group) is larger than the number of zeros you include?
For each group of consecutive ones, the number of characters you need to include to the left will determine how many valid substrings end with that group of ones.
Sum up the number of valid substrings for each group of consecutive ones. This total is the final answer: the total number of substrings with more ones than zeros.

Code Implementation

def count_substrings_with_dominant_ones(binary_string):
    string_length = len(binary_string)
    total_valid_substrings = 0
    
    index = 0
    while index < string_length:
        if binary_string[index] == '1':
            ones_group_length = 0
            group_index = index

            # Find the length of the consecutive ones group
            while group_index < string_length and binary_string[group_index] == '1':
                ones_group_length += 1
                group_index += 1

            # Calculate the number of zeros needed to be less than ones
            zeros_needed = ones_group_length
            left_index = index - 1
            zeros_count = 0

            # Determine how far left to go to form valid substring
            while left_index >= 0 and zeros_count < zeros_needed:
                if binary_string[left_index] == '0':
                    zeros_count += 1
                left_index -= 1

            #This is the number of valid substrings ending at this group.
            total_valid_substrings += (index - left_index - 1)
            index = group_index
        else:
            index += 1

    return total_valid_substrings

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of size n once to identify groups of consecutive ones. For each group, it then iterates backward at most until the beginning of the string to determine the shortest valid substring ending at that group. Although there's a backward iteration, it's bounded by the length of the string in total across all groups, and each character is only visited a constant number of times. Therefore, the overall time complexity is dominated by the initial single pass through the string, resulting in O(n).

Space Complexity

O(N) – The algorithm identifies consecutive groups of ones and their lengths. While the plain English explanation doesn't explicitly state storing these lengths in a list or array, the process of counting valid substrings ending at each group implies storing the start indices of these groups or their lengths for later use. In the worst-case scenario, the input string consists entirely of ones interleaved with zeros (e.g., "1010101"), leading to N/2 groups, which is still proportional to N. Therefore, storing these indices or lengths requires auxiliary space proportional to the input size N. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as there are no substrings to evaluate.
String of length 1 or 2	Check if the single character (or each character) is '1', and increment the count if it is and there are more 1s.
String containing only zeros (e.g., '0000')	Return 0, as no substring can have more ones than zeros.
String containing only ones (e.g., '1111')	Return n*(n+1)/2, as every substring will have more ones than zeros.
String with alternating ones and zeros (e.g., '101010')	Iterate through all substrings, counting ones and zeros and only incrementing count if ones > zeros.
Very long string approaching memory limits	The solution should have O(n^2) complexity, and will require enough memory to store string, handle overflow, consider an algorithm for substring validation that does not create a new string for each substring.
String with integer overflow potential for counting ones or zeros.	Ensure the counting variables (number of ones and number of zeros) are large enough to hold the maximum count or use modulo operation.
String consists only of 1's at the start and the rest are 0's	The algorithm needs to traverse through each substring even with diminishing '1's to find valid combinations.

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 possible length of the binary string?
If the input string is empty or null, what should I return?
By 'dominant ones,' do you mean that the number of ones in the substring must be strictly greater than the number of zeros, or is equality acceptable?
Are there any specific constraints on the characters allowed in the string, or is it guaranteed to only contain '0' and '1'?
Could you provide a small example to illustrate the expected behavior and output format?

Brute Force Solution

Approach

We want to find all sections within a sequence where there are more ones than zeros. The brute force way checks every single possible section to see if it meets the criteria.

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

First, consider every section that starts at the very beginning of the sequence.
Check if the first number alone has more ones than zeros. If so, count it.
Then, check the first two numbers together. If they have more ones than zeros, count that section too.
Continue adding one number at a time to the section, each time checking if the section has more ones than zeros, and counting it if it does.
Once you've checked all the sections that start at the beginning, move on and repeat the process starting from the second number in the sequence.
Keep doing this, moving one number at a time and starting a new set of section checks, until you reach the end of the sequence.
In the end, add up all the sections you counted that had more ones than zeros. This total number is the final answer.

Code Implementation

def count_substrings_with_dominant_ones(sequence):
    total_substrings_with_more_ones = 0

    for starting_index in range(len(sequence)):
        for ending_index in range(starting_index, len(sequence)):

            # Extract the current substring for evaluation.
            current_substring = sequence[starting_index:ending_index + 1]

            number_of_ones = 0
            number_of_zeros = 0

            for bit in current_substring:
                if bit == '1':
                    number_of_ones += 1
                else:
                    number_of_zeros += 1

            # Determine if the substring has more ones than zeros
            if number_of_ones > number_of_zeros:

                # Count substrings that satisfy the condition.
                total_substrings_with_more_ones += 1

    # Returns the final count
    return total_substrings_with_more_ones

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, go through the entire input string and identify all the consecutive groups of ones.
For each group of consecutive ones, determine its length.
Then, consider each group of consecutive ones as the *end* of a valid substring. We'll count how many substrings *ending* with that group are valid.
To do that, for each group, look to the left. How many characters to the left do you need to include in your substring so that the number of ones you have (from your group) is larger than the number of zeros you include?
For each group of consecutive ones, the number of characters you need to include to the left will determine how many valid substrings end with that group of ones.
Sum up the number of valid substrings for each group of consecutive ones. This total is the final answer: the total number of substrings with more ones than zeros.

Code Implementation

def count_substrings_with_dominant_ones(binary_string):
    string_length = len(binary_string)
    total_valid_substrings = 0
    
    index = 0
    while index < string_length:
        if binary_string[index] == '1':
            ones_group_length = 0
            group_index = index

            # Find the length of the consecutive ones group
            while group_index < string_length and binary_string[group_index] == '1':
                ones_group_length += 1
                group_index += 1

            # Calculate the number of zeros needed to be less than ones
            zeros_needed = ones_group_length
            left_index = index - 1
            zeros_count = 0

            # Determine how far left to go to form valid substring
            while left_index >= 0 and zeros_count < zeros_needed:
                if binary_string[left_index] == '0':
                    zeros_count += 1
                left_index -= 1

            #This is the number of valid substrings ending at this group.
            total_valid_substrings += (index - left_index - 1)
            index = group_index
        else:
            index += 1

    return total_valid_substrings

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as there are no substrings to evaluate.
String of length 1 or 2	Check if the single character (or each character) is '1', and increment the count if it is and there are more 1s.
String containing only zeros (e.g., '0000')	Return 0, as no substring can have more ones than zeros.
String containing only ones (e.g., '1111')	Return n*(n+1)/2, as every substring will have more ones than zeros.
String with alternating ones and zeros (e.g., '101010')	Iterate through all substrings, counting ones and zeros and only incrementing count if ones > zeros.
Very long string approaching memory limits	The solution should have O(n^2) complexity, and will require enough memory to store string, handle overflow, consider an algorithm for substring validation that does not create a new string for each substring.
String with integer overflow potential for counting ones or zeros.	Ensure the counting variables (number of ones and number of zeros) are large enough to hold the maximum count or use modulo operation.
String consists only of 1's at the start and the rest are 0's	The algorithm needs to traverse through each substring even with diminishing '1's to find valid combinations.