Count of groups of consecutive 1s in a given Binary String
Given a binary string S of size N, the task is to find the number of groups of 1s only in the string S.
Examples:
Input: S = β100110111β, N = 9
Output: 3
Explanation:
The following groups are of 1s only:
- Group over the range [0, 0] which is equal to β1β.
- Group over the range [3, 4] which is equal to β11β.
- Group over the range [6, 8] which is equal to β111β.
Therefore, there are a total of 3 groups of 1s only.
Input: S = β0101β
Output: 2
Approach: The problem can be solved by iterating over the characters of the string. Follow the steps below to solve the problem:
- Initialize a variable, say count as 0, which stores the number of substrings of 1s in S.
- Initialize a stack say st to store the substring before an index of 1s only.
- Iterate over the characters of the string S, using the variable i and do the following:
- If the current character is 1, push 1 into stack st.
- Otherwise, If st is not empty, increment count by 1. Else Clear st.
- If st is not empty, increment count by 1, i.e If there is a suffix of 1s.
- Finally, print the total count obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of the // groups of 1s only in the binary // string int groupsOfOnes(string S, int N) { // Stores number of groups of 1s int count = 0; // Initialization of the stack stack< int > st; // Traverse the string S for ( int i = 0; i < N; i++) { // If S[i] is '1' if (S[i] == '1' ) st.push(1); // Otherwise else { // If st is empty if (!st.empty()) { count++; while (!st.empty()) { st.pop(); } } } } // If st is not empty if (!st.empty()) count++; // Return answer return count; } // Driver code int main() { // Input string S = "100110111" ; int N = S.length(); // Function call cout << groupsOfOnes(S, N) << endl; return 0; } |
Java
// Java program for the above approach import java.util.Stack; class GFG{ // Function to find the number of the // groups of 1s only in the binary // string static int groupsOfOnes(String S, int N) { // Stores number of groups of 1s int count = 0 ; // Initialization of the stack Stack<Integer> st = new Stack<>(); // Traverse the string S for ( int i = 0 ; i < N; i++) { // If S[i] is '1' if (S.charAt(i) == '1' ) st.push( 1 ); // Otherwise else { // If st is empty if (!st.empty()) { count++; while (!st.empty()) { st.pop(); } } } } // If st is not empty if (!st.empty()) count++; // Return answer return count; } // Driver code public static void main(String[] args) { // Input String S = "100110111" ; int N = S.length(); // Function call System.out.println(groupsOfOnes(S, N)); } } // This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach # Function to find the number of the # groups of 1s only in the binary # string def groupsOfOnes(S, N): # Stores number of groups of 1s count = 0 # Initialization of the stack st = [] # Traverse the string S for i in range (N): # If S[i] is '1' if (S[i] = = '1' ): st.append( 1 ) # Otherwise else : # If st is empty if ( len (st) > 0 ): count + = 1 while ( len (st) > 0 ): del st[ - 1 ] # If st is not empty if ( len (st)): count + = 1 # Return answer return count # Driver code if __name__ = = '__main__' : # Input S = "100110111" N = len (S) # Function call print (groupsOfOnes(S, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the number of the // groups of 1s only in the binary // string static int groupsOfOnes( string S, int N) { // Stores number of groups of 1s int count = 0; // Initialization of the stack Stack< int > st = new Stack< int >(); // Traverse the string S for ( int i = 0; i < N; i++) { // If S[i] is '1' if (S[i] == '1' ) st.Push(1); // Otherwise else { // If st is empty if (st.Count > 0) { count++; while (st.Count > 0) { st.Pop(); } } } } // If st is not empty if (st.Count > 0) count++; // Return answer return count; } // Driver code public static void Main() { // Input string S = "100110111" ; int N = S.Length; // Function call Console.Write(groupsOfOnes(S, N)); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript program for the above approach // Function to find the number of the // groups of 1s only in the binary // string function groupsOfOnes(S, N) { // Stores number of groups of 1s let count = 0; // Initialization of the stack var st = []; // Traverse the string S for (let i = 0; i < N; i++) { // If S[i] is '1' if (S[i] == '1' ) st.push(1); // Otherwise else { // If st is empty if (st.length != 0) { count++; while (st.length != 0) { st.pop(); } } } } // If st is not empty if (st.length != 0) count++; // Return answer return count; } // Driver code // Input var S = "100110111" ; let N = S.length; // Function call document.write(groupsOfOnes(S, N)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)