Count ways to partition a Binary String such that each substring contains exactly two 0s

0 0 5 minutes read

Given binary string str, the task is to find the count of ways to partition the string such that each partitioned substring contains exactly two 0s.

Examples:

Input: str = “00100”
Output: 2
Explanation:
Possible ways to partition the string such that each partition contains exactly two 0s are: { {“00”, “100”}, {“001”, “00”} }.
Therefore, the required output is 2.

Input: str = “000”
Output: 0

Approach: The idea is to calculate the count of 1s between every two consecutive 0s of the given string. Follow the steps below to solve the problem:

Initialize an array, say IdxOf0s[], to store the indices of 0s in the given string.
Iterate over the characters of the given string and store the indices of the 0s into IdxOf0s[].
Initialize a variable, say cntWays, to store the count of ways to partition the string such that each partition contains exactly two 0s.
If the count of 0s in the given string is odd, then update cntWays = 0.
Otherwise, traverse the array IdxOf0s[] and calculate the count of ways to partition the array having each partition exactly two 0s using cntWays *= (IdxOf0s[i] – IdxOf0s[i – 1])
Finally, print the value of cntWays.

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 count of ways to partition
// the string such that each partition
// contains exactly two 0s.
int totalWays(int n, string str)
{
 
    // Stores indices of 0s in
    // the given string.
    vector<int> IdxOf0s;
 
    // Store the count of ways to partition
    // the string such that each partition
    // contains exactly two 0s.
    int cntWays = 1;
 
    // Iterate over each characters
    // of the given string
    for (int i = 0; i < n; i++) {
 
        // If current character is '0'
        if (str[i] == '0') {
 
            // Insert index
            IdxOf0s.push_back(i);
        }
    }
 
    // Stores total count of 0s in str
    int M = IdxOf0s.size();
 
    if (M == 0 or M % 2) {
 
        return 0;
    }
 
    // Traverse the array, IdxOf0s[]
    for (int i = 2; i < M; i += 2) {
 
        // Update cntWays
        cntWays = cntWays * (IdxOf0s[i]
                             - IdxOf0s[i - 1]);
    }
 
    return cntWays;
}
 
// Driver Code
int main()
{
    string str = "00100";
 
    int n = str.length();
 
    cout << totalWays(n, str);
 
    return 0;
}

Java

// Java program for the above approach 
import java.util.*;
class GFG
{
       
// Function to find count of ways to partition 
// the string such that each partition 
// contains exactly two 0s. 
static int totalWays(int n, String str) 
{ 
   
    // Stores indices of 0s in 
    // the given string.
    ArrayList<Integer> IdxOf0s =  
                    new ArrayList<Integer>();
   
    // Store the count of ways to partition 
    // the string such that each partition 
    // contains exactly two 0s. 
    int cntWays = 1; 
   
    // Iterate over each characters 
    // of the given string 
    for (int i = 0; i < n; i++)
    { 
   
        // If current character is '0' 
        if (str.charAt(i) == '0') 
        { 
   
            // Insert index 
            IdxOf0s.add(i); 
        } 
    } 
   
    // Stores total count of 0s in str 
    int M = IdxOf0s.size(); 
    if ((M == 0) || ((M % 2) != 0))
    { 
        return 0; 
    } 
   
    // Traverse the array, IdxOf0s[] 
    for (int i = 2; i < M; i += 2)
    { 
   
        // Update cntWays 
        cntWays = cntWays * (IdxOf0s.get(i) 
                             - IdxOf0s.get(i - 1)); 
    }  
    return cntWays; 
} 
   
// Driver code
public static void main(String[] args)
{
    String str = "00100"; 
    int n = str.length(); 
    System.out.print(totalWays(n, str)); 
}
}
 
// This code is contributed by sanjoy_62.

Python3

# Python3 program for the above approach
 
# Function to find count of ways to partition
# thesuch that each partition
# contains exactly two 0s.
def totalWays(n, str):
     
    # Stores indices of 0s in
    # the given string.
    IdxOf0s = []
 
    # Store the count of ways to partition
    # the such that each partition
    # contains exactly two 0s.
    cntWays = 1
 
    # Iterate over each characters
    # of the given string
    for i in range(n):
         
        # If current character is '0'
        if (str[i] == '0'):
             
            # Insert index
            IdxOf0s.append(i)
 
    # Stores total count of 0s in str
    M = len(IdxOf0s)
 
    if (M == 0 or M % 2):
        return 0
 
    # Traverse the array, IdxOf0s[]
    for i in range(2, M, 2):
         
        # Update cntWays
        cntWays = cntWays * (IdxOf0s[i] -
                             IdxOf0s[i - 1])
 
    return cntWays
 
# Driver Code
if __name__ == '__main__':
     
   str = "00100"
   n = len(str)
    
   print(totalWays(n, str))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach 
using System;
using System.Collections;  
using System.Collections.Generic;  
 
class GFG 
{
 
  // Function to find count of ways to partition
  // the string such that each partition
  // contains exactly two 0s.
  static int totalWays(int n, string str)
  {
 
    // Stores indices of 0s in
    // the given string.
    ArrayList IdxOf0s
      = new ArrayList();
 
    // Store the count of ways to partition
    // the string such that each partition
    // contains exactly two 0s.
    int cntWays = 1;
 
    // Iterate over each characters
    // of the given string
    for (int i = 0; i < n; i++) 
    {
 
      // If current character is '0'
      if (str[i] == '0') 
      {
 
        // Insert index
        IdxOf0s.Add(i);
      }
    }
 
    // Stores total count of 0s in str
    int M = IdxOf0s.Count;
    if ((M == 0) || ((M % 2) != 0)) {
      return 0;
    }
 
    // Traverse the array, IdxOf0s[]
    for (int i = 2; i < M; i += 2) 
    {
 
      // Update cntWays
      cntWays = cntWays * (Convert.ToInt32(IdxOf0s[i]) - 
                           Convert.ToInt32(IdxOf0s[i - 1]));
    }
    return cntWays;
  }
 
  // Driver code
  static public void Main()
  {
    string str = "00100";
    int n = str.Length;
    Console.Write(totalWays(n, str));
  }
}
 
// This code is contributed by Dharanendra L V

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find count of ways to partition
// the string such that each partition
// contains exactly two 0s.
function totalWays(n, str)
{
 
    // Stores indices of 0s in
    // the given string.
    var IdxOf0s = [];
 
    // Store the count of ways to partition
    // the string such that each partition
    // contains exactly two 0s.
    var cntWays = 1;
 
    // Iterate over each characters
    // of the given string
    for (var i = 0; i < n; i++) {
 
        // If current character is '0'
        if (str[i] == '0') {
 
            // Insert index
            IdxOf0s.push(i);
        }
    }
 
    // Stores total count of 0s in str
    var M = IdxOf0s.length;
 
    if (M == 0 || M % 2) {
 
        return 0;
    }
 
    // Traverse the array, IdxOf0s[]
    for (var i = 2; i < M; i += 2) {
 
        // Update cntWays
        cntWays = cntWays * (IdxOf0s[i]
                            - IdxOf0s[i - 1]);
    }
 
    return cntWays;
}
 
// Driver Code
var str = "00100";
var n = str.length;
document.write( totalWays(n, str));
 
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!