CareerCup

Lets call given input string, T and string that contains characters to be removed as S. 1. Create auxiliary array of 26 size representing the character set (alphabets). Set 1 in chars location if char occurs in S else 0
2. Read string T, if index[char]==1 in auxiliary array, then remove the char from string T.

This will be done in O(n) + O(m) = O(n) time complexity with constant space complexity (26 sized array).

does not look like a generalized solution....
"This" is different than "this" , what if the substring changed to "ti". then will you have new array of 26? How will you cover any special characters like "@"

Create a hash table instead of auxiliary array. Hence, the lookup would be O(1)

1. create a hash table with the character to be removed, here i & s
2. 0 - length(str)
if(hash.get(i)!= str.charAt(i)
newstring[destination++]=string[source]

1. create a hash table with the character to be removed, here i & s
2. source = 0 - length(str)
if(hash.get(str.charAt(i))!= str.charAt(i)
newstring[destination++]=string[source]
else
source++

Can someone make the question clearer.
Is it that only when 'i' and 's' appear together, they shud be removed or any occurrence of 'i' and 's' in source string shud be removed.

Are we going to remove given chars or a given string?

void rem_char(char *word,char to_rem)
{
int next_ins = 0,trav = 0;
while(word[trav])
{
  if(word[trav] != to_rem)
    word[next_ins++] = word[trav++];
  else
    trav++;
}
word[next_ins] = '\0';
}

Fast string search algo' should work here. Refer wikipedia

This is a solution in O(n)

public String removeString(String input, String remove) {
		char[] inputArray = input.toCharArray();
		char[] removeArray = remove.toCharArray();
		String newString = "";
		String tmp = "";
		int i, j = 0;
		int removelength = removeArray.length;
		for (i = 0; i < inputArray.length; i++) {
			if (inputArray[i] == removeArray[j]) {
				tmp = tmp + removeArray[j];
				j++;
				if (j == removelength) {
					j = 0;
					tmp = "";
				}
				continue;
			} else if (j > 0) {
				newString = newString + tmp + inputArray[i];
				j = 0;
				tmp = "";
			} else {
				newString = newString + inputArray[i];
			}
		}
		if (j > 0)
			newString = newString + tmp;

		return newString;
	}

Here we parse the 1st string("This is a boy") character by character, and everytime we check with the 1st char of the 2nd String("is" which is 'i' here). Now if we match with it then all we need to do is to compare substring till the size of 2nd string from the current index if the two string are equal if yes then we remove all the character from the 1st string from the current index to the size of the 2nd String.

if at any moment we find that the substring and the 2nd string are not equal the we move our cursor to the next character in the 1st striing and repeate the above steps.

And we can improve this by using finite automata.