Cuente las formas de particionar una string binaria de modo que cada substring contenga exactamente dos 0

Dada la string binaria str , la tarea es encontrar el número de formas de particionar la string de modo que cada substring particionada contenga exactamente dos 0 s.

Ejemplos:

Entrada: str = “00100” 
Salida:  2
Explicación: 
Las formas posibles de particionar la string de modo que cada partición contenga exactamente dos 0 son: { {“00”, “100”}, {“001”, “00”} } . 
Por lo tanto, la salida requerida es 2.

Entrada: str = “000” 
Salida: 0

Enfoque: La idea es calcular la cuenta de 1 s entre cada dos 0 s consecutivos de la string dada. Siga los pasos a continuación para resolver el problema:

• Inicialice una array, digamos IdxOf0s[] , para almacenar los índices de 0 s en la string dada.
• Iterar sobre los caracteres de la string dada y almacenar los índices de los 0 en IdxOf0s[] .
• Inicialice una variable, digamos cntWays , para almacenar el recuento de formas de dividir la string de manera que cada partición contenga exactamente dos 0 s.
• Si el conteo de 0 s en la string dada es impar, actualice cntWays = 0 .
• De lo contrario, recorra la array IdxOf0s[] y calcule la cantidad de formas de dividir la array que tiene cada partición exactamente dos 0 usando cntWays *= (IdxOf0s[i] – IdxOf0s[i – 1])
• Finalmente, imprima el valor de cntWays .

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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

<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>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(N)