Number of Substrings in String of 0s and 1s that have K 1s

In this article, we have explored algorithm to find the Number of Substrings in a String of 0's and 1's that have 'K' number of 1's.

Table of contents:

1. Problem Statement
2. Brute Force approach
3. Efficient approach

Pre-requisite:

• Prefix Sum Array

Problem Statement

Input :
i) A String of 0's and 1's
ii) A integer 'K'

Output : Number of substrings that have 'K' number of 1's

Example 1:

Input : "101010",K=2
Output : 6 

Substrings are "101" [0,2],"1010" [0,3],"0101" [1,4],"01010" [1,5],"101" [2,4] and "1010" [2,5]

Example 2:

Input : "1001",K=2
Output : 1
Substring is "1001" [0,3]

In this problem,we have to count the number of substrings in a given string of 0's and 1's, that contains exactly K 1's.

Method 1 (Brute Force Method)

Initially, you may think to check all the substrings one by one and then count number of 1's in each substring and if numner of 1's equal to K then count this substring.That will be a bruteforce method and its time complexity will be very high.

Implementation of BruteForce Method(C++)

#include<bits/stdc++.h> 
using namespace std; 

vector<string> substring;

int kones(int k)
{
    int i,j;
    int cnt=0,ans=0;
    
    //traversing through all the substrings
    for(i=0;i<substring.size();i++)    
    {
        cnt=0;
        
        //traversing through i'th substring
        for(j=0;j<substring[i].length();j++)
        {
            if(substring[i][j]=='1')
                cnt++;
        }
        
        //if count of 1 in substring,increment the answer
        if(cnt==k)
            ans++;
    }
    
    return ans;
}

// Function to store all substrings in a vector 
void subString(string s, int n) 
{ 
    int i,j;
    
	for(i=0;i<n;i++) 
	{	
	    for( j=1;j<=n-i;j++) 
		{	
			substring.push_back(s.substr(i,j));
		}
	}	
} 

// Driver program 
int main() 
{ 
	string s;
	int k;
	
	cin>>s>>k;
	
	subString(s,s.length()); 
	
	int ans=kones(k);
	
	cout<<"Number of substrings are:"<<ans<<"\n";
	
	return 0; 
} 

Input 1

101010
2

Output 1

Number of substrings are:6

Complexity Analysis

Time Complexity : O(n^3)
Space Complexity : O(n^2)

Time Complexity is O(n^3),because for finding all substrings, three nested loops work( substr() also take O(n)).

Space Complexity is O(n^2),because,number of non-empty substrings in any substring is n*(n+1)/2.Thus size of vector depends on input string length.

Seriously,this was not the method you were searching for.Let's start heading towards the efficient approach!!.

Method 2 (Efficent Approach)

If we see this problem from another persepective,we will be able to conclude that we have to just find the substrings whose sum is equal to K, because input string only consist of 0's and 1's.Now,this can be solved easily by using the prefix sum array concept.

Firstly,we will create a prefix sum array that will keep record of sum of 1's upto any index.Now,we will loop through this array and whenever the sum will be greater or equal to K,we will stop and if the sum at current index is (K+a),then substring sum from any index where sum is 'a',will be equal to K.Therefore, we just have to count index where sum is 'a' before current index and add this to final result.

Now, consider the following example for better explanation.

Input string="101010"
K=2

Prefix sum array=[ 1 , 1 , 2 , 2 , 3 , 3 ]

Now loop through this array.
Initialize result=0

At index 0:
    sum=1,which is smaller than K,so the result will not change.

At index 1:
    sum=1,which is again smaller than K,so the result will not change.
    
At index 2:
    sum=2,which is equal to K,and a=0.So total index where a=0 is 1,which is the
    current index. Therefore, result+=1
    result till now = 1
    
At index 3:
    sum=2,which is again equal to K,and a=0.So total indices where a=0 is 1,which is
    the current index. Therefore, result+=1
    result till now = 2
    
At index 4:
    sum=3,which is greater than K, and a=1 here.So total indices where a=1 is
    2,which are 0 and 1.Therefore, result+=2
    result till now = 4
    
At index 5:
    sum=3,which is greater than K, and a=1 here.So total indices where a=1 is
    2,which are 0 and 1.Therefore, result+=2
    result till now = 6

Final result = 6

Now,in the code we will keep track of the frequency of each sum rather than keeping the sum upto each index.

Implementation(C++)

#include<bits/stdc++.h>
using namespace std;

int numberofsubstring( string s, int K)
{
    int len=s.length();
    int freq[len+1] = {0};     //for keeping track of frequency of sum
    int result=0;             //final result
    int countone=0;          //for keeping track os sum of digits.
    
    //for a=0,the frequency will always be 1.
    freq[0]=1;
    
    for(int i=0;i<len;i++)
    {
        if(s[i]=='1')       //sum will only increase,when 1 will be detected
            countone++;
        
        if(countone>=K)
        {
            //count all indices where the sum is 'a' and a=countone-K
            result+=freq[(countone-K)]; 
        }
        
        //Increment the frequency of current sum by 1
        freq[countone]++;
    }
    
    return result;
}

//main
int main()
{
    string s;
    int K;
    
    cin>>s;
    cin>>K;
    
    cout<<"Number of substrings are:"<<numberofsubstring(s,K);
    
    return 0;
}

Input 1

1001
2

Output 1

Number of substrings are:1

Input 2

101010
2

Output 2

Number of substrings are:6

Complexity Analysis

Time Complexity : O(n)
Space Complexity : O(n)

Time Complexity is O(n),because only a single traversal of string is required.
Space Complexity is O(n),because,the size of freq[] array depends on the input string length.

That's all. I hope you find it informative!