Given two strings, How do we delete all the characters in the first string which are present in the second string?
Find the character set of the string. Create a Boolean array of size equal to the character set size. If the character set is ASCII, the size is 256. This array will be indexed by the character itself.
For example, array[‘c’] stores whether character ‘c’ is present in the string are not.
Iterate through each character of the second string, update the corresponding Boolean flag in the array to true.
Now loop through all the characters from the input string and retain the only characters not present in the mask.
Following is the C++ program to do it. This code runs in O(n) time and constant space. I have modified the input string itself without creating an auxiliary array.
#include <iostream>
#include <string>
using namespace std;
void removeChars( char * input, char * mask)
{
//initialize all the chars to false
bool charPresent[256] = {false};
int i;
//mark all the mask characters to true.
for( i = 0; mask[i]; ++i)
{
charPresent[mask[i]] = true;
}
int resInd = 0; //to track result string
int ind = 0;
while( input[ind] )
{
//Add the character only if it is not present in mask
if( !charPresent[ input[ind] ] )
{
input[resInd++] = input[ind];
}
ind++;
}
input[resInd] = ' '; //Null terminator to end the string
}
int main()
{
char inputStr[] = "This is a test";
char maskStr[] = "aeiou";
removeChars( inputStr, maskStr);
cout<<inputStr;
return 0;
}