Given a string S consisting of characters 0, 1, and ‘?’, the task is to count all possible combinations of the binary string formed by replacing ‘?’ by 0 or 1.
Examples:
Input: S = “0100?110”
Output: 2
Explanation: Replacing each ‘?’s with ‘1’ and ‘0’, the count of such strings formed will be equal to “01001110” and “01000110”. Therefore, the total count of such strings formed is 2.Input: S = “00?0?111”
Output: 4
Approach: The given problem can be solved based on the following observations:
- Since each ‘?’ can be replaced by ‘0’ or ‘1’, two possible choices exist for every ‘?’ character.
- Now, the task reduces to finding the count of ‘?’s, say count.
- Therefore, the total number of different strings that can be formed is 2count.
Follow the steps below to solve the problem:
- Count the number of occurrences of ‘?’, say count
- Print the value of 2count as the resultant combination of the strings formed.
Below is the implementation of the above approach:
C++14
#include <bits/stdc++.h>using namespace std;//Function to count all possible//permutations of the string svoid 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 Codeint main(){ //Given string S string s = "0100?110"; //Function call to count //the number of permutations countPermutations(s); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to count all possible// permutations of the string sstatic 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 Codepublic 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
# Python3 program for the above approach# Function to count all possible# permutations of the string sdef 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 Ss = "0100?110"# Function call to count# the number of permutationscountPermutations(s)# This code is contribute by mohit kumar 29. |
C#
// C# program for above approachusing System;public class GFG { // Function to count all possible// permutations of the string sstatic 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 codepublic 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. |
Javascript
<script>//Function to count all possible//permutations of the string sfunction 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 Svar s = "0100?110";//Function call to count//the number of permutationscountPermutations(s);</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Here you will find 77274 additional Information on that Topic: geeksforgeeks.org/count-permutations-possible-by-replacing-characters-in-a-binary-string/ […]