Cuente las permutaciones posibles reemplazando ‘?’ caracteres en una string binaria

Dada una string S que consta de los caracteres 0 , 1 y ‘?’ , la tarea es contar todas las combinaciones posibles de la string binaria formada reemplazando ‘?’ por 0 o 1 .

Ejemplos:

Entrada: S = “0100?110”
Salida: 2
Explicación: Reemplazando cada ‘?’ con ‘1’ y ‘0’, el conteo de dichas strings formadas será igual a “01001110” y “01000110”. Por lo tanto, la cuenta total de dichas strings formadas es 2.

Entrada: S = “00?0?111”
Salida: 4

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• Dado que cada ‘?’ puede ser reemplazado por ‘0’ o ‘1’ , existen dos opciones posibles para cada ‘?’ personaje.
• Ahora, la tarea se reduce a encontrar el conteo de ‘?’ s, decir contar .
• Por lo tanto, el número total de strings diferentes que se pueden formar es de 2 ^cuentas .

Siga los pasos a continuación para resolver el problema:

• Cuente el número de ocurrencias de ‘?’ , di cuenta
• Imprime el valor de 2 ^count como la combinación resultante de las strings formadas.

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

#include <bits/stdc++.h>
 
using namespace std;
 
//Function to count all possible
//permutations of the string s
void countPermutations(string s){
 
    //Stores frequency of the
    //character '?'
    int count = 0;
 
    //Traverse the string
    for (char i:s){
        if (i == '?')
            count += 1;
      }
 
    //Print the answer
    cout<<pow(2,count);
}
 
//Driver Code
int main()
{
  //Given string S
  string s = "0100?110";
 
  //Function call to count
  //the number of permutations
  countPermutations(s);
 
  return 0;
}

// Java program for the above approach
class GFG{
 
// Function to count all possible
// permutations of the string s
static void countPermutations(String s)
{
 
    // Stores frequency of the
    // character '?'
    int count = 0;
 
    // Traverse the string
    for (char i : s.toCharArray())
    {
        if (i == '?')
            count += 1;
      }
 
    // Print the answer
    System.out.print((int)Math.pow(2,count));
}
 
 
// Driver Code
public static void main(String[] args)
{
     
    // Given string S
  String s = "0100?110";
 
  // Function call to count
  // the number of permutations
  countPermutations(s);
}
}
 
// This code is contributed by code_hunt.

# Python3 program for the above approach
 
# Function to count all possible
# permutations of the string s
def countPermutations(s):
 
    # Stores frequency of the
    # character '?'
    count = 0
 
    # Traverse the string
    for i in s:
        if i == '?':
 
            # Increment count
            count += 1
 
    # Print the answer
    print(2**count)
 
# Driver Code
 
# Given string S
s = "0100?110"
 
# Function call to count
# the number of permutations
countPermutations(s)
 
# This code is contribute by mohit kumar 29.

// C# program for above approach
using System;
 
public class GFG
{
   
// Function to count all possible
// permutations of the string s
static void countPermutations(string s)
{
 
    // Stores frequency of the
    // character '?'
    int count = 0;
 
    // Traverse the string
    foreach (char i in s)
    {
        if (i == '?')
            count += 1;
      }
 
    // Print the answer
    Console.WriteLine(Math.Pow(2,count));
}
 
// Driver code
public static void Main(String[] args)
{
   
    // Given string S
  string s = "0100?110";
 
  // Function call to count
  // the number of permutations
  countPermutations(s);
}
}
 
// This code is contributed by splevel62.

<script>
 
 
//Function to count all possible
//permutations of the string s
function countPermutations(s){
 
    //Stores frequency of the
    //character '?'
    var count = 0;
 
    //Traverse the string
    for(var i =0; i< s.length; i++)
    {
        if (s[i] == '?')
            count += 1;
    }
 
    //Print the answer
    document.write( Math.pow(2,count));
}
 
//Driver Code
 
//Given string S
var s = "0100?110";
 
//Function call to count
//the number of permutations
countPermutations(s);
 
 
</script>

2

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