CareerCup

Hardcode an array of 128 bools to represent Ascii chars. bool a[128]
Set each location to false a[0] = false ....
This represents characters that are not to be removed
Fill in other locations with chars to remove ie 'A' a[69] = true

std::string newstr;
for ( int i=0; i<origstr.Length; i++ )
if ( a[origstr[i]] == false ) newstr += a[origstr[i] );

O(n+128) = O(n);

Hrm; but O(n) + O(m) /is/ sort of O(n) (assuming similar-length strings, O(2n) == O(n)).

you can't do it without go through the str2, so O(n+m) is the correct answer. may be he means space complexity in O(n)

bit map for str1 chars

Use suffix trees to preprocess. Construction of suffix trees can be done in O(n) and then searching depends on what pattern you want to search.

I dont think building a suffix tree is a good solution as you need to identify all the characters in str2 that occur in str1. the characters of str2 can be spread out in str1
eg:
str1= "monkeydonkey" str2="okden"
Suffix tree can be used to find out the occurance of sub string str2 within str1
I am thinking more like finding the longest common subsequence.
Its a dynamic programming problem

if they are sorted, we can do it in O(n)

Can we do something like this:

let str1 = "hello world" and str2="wo1". Now he wants us to remove all characters in str1 that occur in str2. so we remove the characters "w" and "o" from str1. we dont remove "1" since it doesnt occur in str1.

char* ptr1 = &str1[0] and char * ptr2 = &str2[0];

so, while(*ptr1 && *ptr2)
{
if(*ptr2 == *ptr1) {
delete from str1 the character pointed by ptr1;
ptr2++;
}

ptr1++;

if(ptr1 == NULL || ptr2 == NULL)
break;
}

this is O(n).. or am i missing something here?