Generate all strings by replacing # with 0 and 1

Updated

Write program to replace every ‘#’ symbol with a binary number 0 and 1 and generate all possible combination

Examples :

Input : 11#1
Output : 1101 1111

Input : 1#1#
Output : 1010 1011 1110 1111

Approach :

In this problem we are first going to store the index of all the '#' in string,in the
vector idx, and also there count in length l.

Then we are going to initialize a string as all 0s and of length l as bin.
after that we are going to replace the '#' with bin,and after replacing print the 
string and find next binary number and looping  it for 2^l to get all permutations(2^l).
Also BinNext is used to find next binary number as a string,

Implementation :

//C++ program to replace every '#' symbol with a binary number 0 and 1 and generate all possible combination
#include<bits/stdc++.h>
using namespace std;

//Function to find next binary number as a string 
string BinNext(string num) 
{ 
	int i,l = num.size(); 
	// examine bits from the right 
	for (i=l-1; i>=0; i--) 
	{ 
		// if '0' is encountered, convert 
		// it to '1' and then break 
		if (num.at(i) == '0') 
		{ 
			num.at(i) = '1'; 
			break; 
		} 

		// otherwise convert '1' to '0' 
		else
			num.at(i) = '0'; 
	} 

	
	// final binary representation 
	// of the required integer 
	return num; 
} 

//Generate possible strings function
void printCOMB(string s)
{
    int sz = s.length(),length = 0;//sz to store size of string
    vector< int > idx;              //vector idx to store index of '#'' in code
    for(int i = 0; i < sz; i++)
    {
        if(s[i] =='#')
        idx.push_back(i) , length++;//pushing the index of '#'
    }
    //bin is going to store current binary string that
    //is going to replace the '#'
    string bin(length,'0');         //initializing the string with all zeros of length
      
    //loop for all permutation in sorted order over 2^length
    for(int j = 1;j <= (1<<length);j++)
    {   //loop for replacing the '#' with bin
        for(int i = 0;i < length;i++)
            s[idx[i]]=bin[i];
        cout<<s<<" ";
        //incrementing the bin as a binary string 
        //example 100-->101,010-->011
        bin=BinNext(bin);
    }
    
}

//Driver function
int main()
{
    string s = "1#1#";
    printCOMB(s);
}

Output :  

1010 1011 1110 1111

Time Complexity : O(2^n) Space complexity : O(n)

Comment
Next tutorial
Mithlesh Upadhyay Published 16 Nov 2026 · 2 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials