Count of groups of consecutive 1s in a given Binary String

GAZAL ARORA
Last Updated: May 13, 2022

Question

You are given a Binary String S. Return the number of groups in S, containing 1s only.

Input:    A string S, and an integer N, representing the length of S.
Output: An integer returning the count of groups in S containing only 1s.
 


Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 



Example:
Input: S = 1010011101,  N = 10
Output: 4

Explanation: 

The following four groups are of 1s only:

  1. The group over the range [0, 0] is equal to “1”.
  2. The group over the range [2, 2] is equal to “1”.
  3. The group over the range [5, 7] is equal to “111”.
  4. The group over the range [9, 9] is equal to “1”.

Solution

Recommended: Please try to solve it yourself first before moving on to the solution.

The idea is simple: We will solve it by simply iterating over the string and maintaining a stack for the group of 1s.

To solve the problem, follow the steps mentioned below:

  • Initialize a variable count as 0 to keep track of the number of substrings of 1s in S.
  • To store the substring of 1s, create a stack called st.
  • Using the variable i, iterate over the characters of the string S and perform the following:
    • Push 1 onto stack st if the current character is 1.
    • Otherwise, if st isn't empty, add 1 to count. Else Clear st.
    • If st is not empty, increase count by one, i.e., if a suffix of 1s exists.
  • Return count.
     

C++  code

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

int countGroupsOfOnes(string S, int N)
{
stack<int> st;
int count = 0;

for (int i = 0; i < N; i++) {

if (S[i] == '1')
st.push(1);


else {
if (st.empty() == false) {
count++; 
while (st.empty() == false) {
st.pop();
}
}
}
}

if (!st.empty())
count++;

return count;
}

int main()
{
// Input
string S = "1010011101";
int N = 10;

cout << countGroupsOfOnes(S, N) << endl;
return 0;
}

Output

Time Complexity: O(N)

Auxiliary Space: O(N)

Key takeaways

In this article, we solved an array question using stacks. We counted the number of groups in the array that contained only 1s.
You can learn more about stacks from here.

Challenge: Can you solve it without using stack but in O(N) time? 

Apart from this, you can use CodeStudio to practice a wide range of DSA questions typically asked in interviews at big product-based companies. It will assist you in mastering efficient coding techniques and provide you with interview experiences from scholars in large product-based companies.
Happy Coding!

Was this article helpful ?
0 upvotes