Count of All Substrings in a Binary String in Which Count of 1’s is Strictly More than the Count of 0’s

Vaibhav Agarwal
Last Updated: Jun 20, 2022
Difficulty Level :
MEDIUM

Introduction

Strings are one of the most popular Data Structures as well as one of the most basic ones. A substring is a contiguous sequence that is found in a string. In this problem, we are given a binary string and have to find the number of substrings in which the number of ones is strictly greater than zero. As it is with almost every other problem there is this problem also has multiple ways to how we can solve it. We start with the most intuitive solution and move on to the most optimal way. 

Let's get right to it

Problem Statement

The problem states that we are given a binary string, and we need to count the total number of possible substrings in which the count of 1’s is strictly greater than the count of 0’s. 

For example, for a string “101” the substrings with the number of 1s strictly greater than the number of 0s would be “1”, “1” and, “101” having (1,0), (1,0) and, (2,1) as the (number of 1s, number of 0s) respectively. 

 

 

Prerequisites: 

 

To solve this problem, first try this problemCount Inversions Problem. 

We will discuss the efficient approach, along with a sample example and c++ code. 

Sample Examples

Example - 1:

Input :
String str = “110011” 
Output: All substrings in which the count of 1’s is more than the count of 0’s
are 11.
Explanation: 
Substring in which count of 1’s is strictly greater than the count of 0’s are:  
1. str[0] - str[0],
2. str[1] - str[1],
3. str[0] - str[1],
4. str[0] - str[2], 
5. str[0] - str[5], 
6. str[0] - str[4], 
7. str[1] - str[5], 
8. str[3] - str[5],
9. str[4] - str[4], 
10. str[4] - str[5], 
11. str[5] - str[5]. 

 

Example - 2:

Input :
String str = “101” 
Output: All substrings in which the count of 1’s is more than the count of 0’s
are 3.
Explanation: 
Substring in which count of 1’s is strictly greater than the count of 0’s are:  
1. str[0] - str[0],
2. str[0] - str[2],
3. str[2] - str[2].

 

Brute Force Approach

In the brute force approach, the simplest way to do this is to generate all possible substrings and then count a number of 1’s and 0’s in each substring. Then print the count of those substrings which satisfy the above condition. 

Implementation in C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// function to check if the current
// subsequence satisfies the condition or not.
bool checkConditon(string input){
    int n = input.size();
    int countZero = 0, countOne = 0;
    for(int i=0;i<n;i++){
        if(input[i]=='0'){
            countZero++;
        }else{
            countOne++;
        }
    }
    return countOne>countZero;

}
// function to generate all possible subsequence
void GenerateAllSubstrings(string input, int n){
    int count = 0;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            string temp = "";
            for(int k=i;k<=j;k++){
                temp += input[k];
            }
            // calling the checkCondtition function
            if(checkConditon(temp)){
                count++;
            }
        }
    }
    cout << count << endl;
}
// Driver code
int main(){
    string input = "1100111";
    GenerateAllSubstrings(input, 7);
    return 0;
}

 

Output: 

18

Implementation in Java

// Java program for the above approach
import java.util.*;
class solution{
   // function to check if the current
   // subsequence satisfies the condition or not.
   boolean checkConditon(String input){
       int n = input.length();
       int countZero = 0, countOne = 0;
       for(int i=0;i<n;i++){
           if(input.charAt(i)=='0'){
               countZero++;
           }else{
               countOne++;
           }
       }
       return countOne>countZero;
   
   }
   // function to generate all possible subsequence
   void GenerateAllSubstrings(String input, int n){
       int count = 0;
       for(int i=0;i<n;i++){
           for(int j=i;j<n;j++){
               String temp = "";
               for(int k=i;k<=j;k++){
                   temp += input.charAt(k);
               }
               // calling the checkCondtition function
               if(checkConditon(temp)){
                   count++;
               }
           }
       }
       System.out.println(count);
   }
   // main function
   public static void main(String[] args ){
       String input = "1100111";
       solution obj = new solution();
       obj.GenerateAllSubstrings(input, 7);
   }
}    

Output: 

18

Implementation in Python

# python program for the above approach
# function to check if the current
# subsequence satisfies the condition or not.
def checkConditon(input):
   n = len(input)
   countZero = 0
   countOne = 0
   for i in range(n):
       if(input[i] == '0'):
           countZero += 1
       else:
           countOne += 1
  
   return countOne > countZero

# function to generate all possible subsequence
def GenerateAllSubstrings(input, n):
   count = 0
   for i in range(n):
       for j in range(i, n):
           temp = ""
           for k in range(i, j+1):
               temp += input[k]
           
           # calling the checkCondtition function
           if(checkConditon(temp)):
               count += 1
     
   print(count)

# Driver code
def main():
   input = "1100111"
   GenerateAllSubstrings(input, 7)
   
# calling main method
main()

Output: 

18

Complexity Analysis

Time Complexity: O(N^3)

Explanation: As there can be N*(N-1) substrings possible, and to count a number of 1’s and 0’s in each substring it will take O(N) time, so the total time complexity is O(N^3).

Space ComplexityO(1)

Explanation: No extra space is used.

Efficient Approach

To find all substrings in which the count of 1’s is more than the count of 0’s

We will first create one temporary array, let's say, pref[], and traverse the string, if for any i, str[i] == ‘1’, then we will put 1 into the temporary array, and if str[i] == ‘0’, we will put -1 into the temporary array. Then we will convert this temporary array into its prefix sum array. 

For Ex: 

str = “1100111”

Pref[] = [1,2,1,0,1,2,3]

We have created the pref array according to the algorithm explained above. 

Initially Replacing ‘1’ with 1, and ‘0’ with -1.

Pref[] = [1,1,-1,-1,1,1,1].

Converting this array into prefix sum array. 

Pref[] = [1,2,1,0,1,2,3]. 

 

Now if we take a closer look at the prefix array, and take any indexes, let's say i and j, 

If arr[j] < arr[i] for j<i, it means that number of 1’s between indexes j and i, is strictly greater than number of 0’s, then only arr[i] is greater than arr[j]. 

 

In the above example, let take i = 5, and j = 3, then arr[i] = 2, and arr[j] = 0,

Now between j and i, there are 1-0’s and 2-1’s, hence arr[i] > arr[j]. 

Steps of Algorithm

  1. Create a temporary array, say pref[] to store 1 and -1. 
  2. Traverse the string str, and if str[i] == ‘1’, then pref[i] = 1, otherwise str[i] == ‘0’ and pref[i] = -1. 
  3. Create a pref sum array of Pref[]. 
  4. Now this problem is reduced to finding a number of pairs i, and j, where arr[i]>arr[j] and i>j, which is very much similar to the count inversion problem. 

Implementation in C++

/// C++ program for all substrings in which the count of 1’s is more than the count of 0’s
#include <bits/stdc++.h>
using namespace std;

// Function to merge two partitions
// such that the merged array is sorted
int merge(int *v, int left, int mid, int right)
{
    vector<int> temp(right - left + 1);
    int i = left;
    int j = mid + 1;
    int k = 0;
    int cnt = 0;
    int countInversion = 0;
    while (i <= mid && j <= right) {
        if (v[i] <= v[j]) {
            temp[k++] = v[i++];
        }
        else {
            // Counting inversions
            countInversion += (mid - i + 1);
            temp[k++] = v[j++];
        }
    }

    while (i <= mid)
        temp[k++] = v[i++];

    while (j <= right)
        temp[k++] = v[j++];
    k = 0;
    for (int a = left; a <= right; a++) {
        v[a] = temp[k++];
    }
    return countInversion;
}

// Function to implement merge sort
int mergeSort(int *v, int left,int right){
    int a=0,b=0,c=0;
    if(left<right){
        int mid = (left + right) / 2;
        a = mergeSort(v, left, mid);
        b = mergeSort(v, mid + 1, right);
        c = merge(v, left, mid, right);
    }
    return a+b+c;
}

// Function to calculate number of
// inversions in a given array
int CountInversions(int *v, int n)
{
    // Calculate the number of inversions by calling mergeSort
    return mergeSort(v, 0, n - 1);
}

// Function to count the number of
// substrings that contains more 1s than 0s
int getSubsCount(string& str){
    int n = str.size();
    int pref[n];

    // putting 1 for '1' and -1 for '0' as explained in the approach
    for(int i=0;i<n;i++){
        if(str[i]=='0')
            pref[i] = -1;
        else
            pref[i] = 1;
    }
    // converting into prefix sum array
    for(int i=1;i<n;i++){
        pref[i] += pref[i-1];// Stores the count of valid substrings];
    }
    // Stores the count of valid substrings
    int count = 0;
    for(int i=0;i<n;i++){
        if(pref[i]>0)
            count++;
    }
    int j = n-1;
    for(int i=0;i<j;i++,j--){
        swap(pref[i],pref[j]);
    }
    return count + CountInversions(pref,n);
}

// Driver Code
int main()
{

    // Given Input
    string input = "1100111";

    // Function Call
    int ans = getSubsCount(input);

    cout << "Total substring in which count of 1s is strictly greater than the count of 0s is " << ans << endl;

    return 0;
}

 

Output: 

Total substring in which count of 1s is strictly greater than the count of 0s is 18

Implementation in Python

# Python 3 program to count inversions in an array


# Function to Use Inversion Count


def mergeSort(arr, n):
    # A temp_arr is created to store
    # sorted array in merge function
    temp_arr = [0]*n
    return _mergeSort(arr, temp_arr, 0, n-1)


# This Function will use MergeSort to count inversions



def _mergeSort(arr, temp_arr, left, right):


    # A variable inv_count is used to store
    # inversion counts in each recursive call


    inv_count = 0


    # We will make a recursive call if and only if
    # we have more than one elements


    if left < right:


        # mid is calculated to divide the array into two subarrays
        # Floor division is must in case of python


        mid = (left + right)//2


        # It will calculate inversion
        # counts in the left subarray


        inv_count += _mergeSort(arr, temp_arr,
                                left, mid)


        # It will calculate inversion
        # counts in right subarray


        inv_count += _mergeSort(arr, temp_arr,
                                mid + 1, right)


        # It will merge two subarrays in
        # a sorted subarray


        inv_count += merge(arr, temp_arr, left, mid, right)
    return inv_count


# This function will merge two subarrays
# in a single sorted subarray



def merge(arr, temp_arr, left, mid, right):
    i = left     # Starting index of left subarray
    j = mid + 1 # Starting index of right subarray
    k = left     # Starting index of to be sorted subarray
    inv_count = 0


    # Conditions are checked to make sure that
    # i and j don't exceed their
    # subarray limits.


    while i <= mid and j <= right:


        # There will be no inversion if arr[i] <= arr[j]


        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            k += 1
            i += 1
        else:
            # Inversion will occur.
            temp_arr[k] = arr[j]
            inv_count += (mid-i + 1)
            k += 1
            j += 1


    # Copy the remaining elements of left
    # subarray into temporary array
    while i <= mid:
        temp_arr[k] = arr[i]
        k += 1
        i += 1


    # Copy the remaining elements of right
    # subarray into temporary array
    while j <= right:
        temp_arr[k] = arr[j]
        k += 1
        j += 1


    # Copy the sorted subarray into Original array
    for loop_var in range(left, right + 1):
        arr[loop_var] = temp_arr[loop_var]


    return inv_count



def getSubsCount(str):
    n = len(str)
    pref = [0 for i in range(n)]


    # putting 1 for '1' and -1 for '0' as explained in the approach
    for i in range(n):
        if(str[i]=='0'):
            pref[i] = -1
        else:
            pref[i] = 1
   
    # converting into prefix sum array
    for i in range(1, n):
        pref[i] += pref[i-1] # Stores the count of valid substrings];
   
    # Stores the count of valid substrings
    count = 0
    for i in range(n):
        if(pref[i]>0):
            count += 1
           
    j = n-1
    i = 0
    while i<j:
        pref[i],pref[j] = pref[j], pref[i]
        i += 1
        j -= 1
   
    return count + mergeSort(pref,n)



# Driver Code


def main():
    # Given Input
    inp = "1100111"
    # Function Call
    ans = getSubsCount(inp)
    print(ans)



main()

Output: 

18

Implementation in Java

public class coding_ninjas {
public static int merge(int[] v, int left, int mid, int right)
{
    int[] temp=new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    int cnt = 0;
    int countInversion = 0;
    while (i <= mid && j <= right) {
        if (v[i] <= v[j]) {
            temp[k++] = v[i++];
        }
        else {
            // Counting inversions
            countInversion += (mid - i + 1);
            temp[k++] = v[j++];
        }
    }
    while (i <= mid)
        temp[k++] = v[i++];
    while (j <= right)
        temp[k++] = v[j++];
    k = 0;
    for (int a = left; a <= right; a++) {
        v[a] = temp[k++];
    }
    return countInversion;
}
// Function to implement merge sort
public static  int mergeSort(int[] v, int left,int right){
    int a=0,b=0,c=0;
    if(left<right){
        int mid = (left + right) / 2;
        a = mergeSort(v, left, mid);
        b = mergeSort(v, mid + 1, right);
        c = merge(v, left, mid, right);
    }
    return a+b+c;
}
// Function to calculate number of
// inversions in a given array
public static int CountInversions(int[] v, int n)
{
    // Calculate the number of inversions by calling mergeSort
    return mergeSort(v, 0, n - 1);
}
// Function to count the number of
// substrings that contains more 1s than 0s
public static int getSubsCount(String str){
    int n = str.length();
    int[] pref=new int[n];
    // putting 1 for '1' and -1 for '0' as explained in the approach
    for(int i=0;i<n;i++){
        if(str.charAt(i)=='0')
            pref[i] = -1;
        else
            pref[i] = 1;
    }
    // converting into prefix sum array
    for(int i=1;i<n;i++){
        pref[i] += pref[i-1];// Stores the count of valid substrings];
    }
    // Stores the count of valid substrings
    int count = 0;
    for(int i=0;i<n;i++){
        if(pref[i]>0)
            count++;
    }
    int j = n-1;
    for(int i=0;i<j;i++,j--){
        int temp;
        temp=pref[i];
        pref[i]=pref[j];
        pref[j]=temp;
    }
    return count + CountInversions(pref,n);
}
// Driver Code
public static void main (String ar[])
{
    // Given Input
    String input = "1100111";
    // Function Call
    int ans = getSubsCount(input);
    System.out.println("Total substring in which count of 1s is strictly greater than the count of 0s is " +ans);
}
}

Output: 

Total substring in which count of 1s is strictly greater than the count of 0s is 18

Complexity Analysis

Time Complexity: O(NlogN)

Explanation: The list of size N is divided into a max of LogN parts, and the merging of all sublists into a single list takes O(N) time, the worst-case run time of this algorithm is O(NLogN). Therefore all substrings in which the count of 1’s is more than the count of 0’s can be find out in O(NlogN) time complexity. 

Space ComplexityO(N)

Explanation: As we are creating pref[], so it is taking O(N) space extra. 

Frequently Asked Questions

Which sorting algorithm is used when we sort using STL? 

The sorting algorithm used in STL sort() is IntroSort. Introsort is a hybrid sorting algorithm that uses three sorting algorithms to minimize the running time. These algorithms are quicksort, Heapsort, and Insertion Sort.

What is the worst, average, and best case time complexity of merge sort? 

Merge sort always have O(NlogN) in all the cases, because we always divide the array into maximum LogN parts, and then again merge them in O(N) time complexity, so overall time complexity is constant, i.e, O(NlogN). 

How many substrings are possible of a string of length N? 

There can be a possibility of N*(N-1)/2 substring of a string of length N.

Conclusion

In this article, we discussed the problem of finding all substrings in which the count of 1’s is more than the count of 0’s in a given binary string. Our efficient approach uses the count inversion problem technique. We hope you understand the problem and solution properly. Now you can do more similar questions. 

You can try out some of the basic string problems by following this link.

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, etc. along with some Contests and Interview Experiences only on CodeStudio

Thank you for reading. 

Until then, Keep Learning and Keep Coding.
 

Was this article helpful ?
1 upvote