CareerCup

I feel KMP algorithm solves this problem, please refer to below link:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

#include<stdio.h>

int main()
{
char str[] = "xyztheabc";
char st[] = "the";
int i = 0;
int j =0;
int len = strlen(str);

int x=0, y=0;

printf ("\nlen - %d\n",strlen(st));

for(i=0;i<len;i++)
{
if(str[i] == st[j])
{
j++;
printf ("%d\t%d\n",i,j);
}
else if (j>0)
{
j=0;
i--;
}

if(j == strlen(st))
break;
}

if(j == (strlen(st)))
{
printf("\nYES\n");
x = i-2;
y = x + j;
for(;y<len;y++,x++)
str[x] = str[y];
str[x] = '\0';
printf ("\n\n Altered - %s\n",str);
else
printf("\nNO\n");


}


** This code does both sub string finding then removal as well **

Test Cases
1. Any input2 with length(input2) > length(input1) should fail
2. input2 = input1 should result in 0 string
3. Give input1 and input2 as null, it should return nothins
4. If input2 is null and input1 is not null, output is same as input1
4. If input2 is not null and inout is null, output should be null

this is tough indeed. All I can think of is O(n^m), I am sure there is a better solution. what is it? n= length of input1 and m = length of input2.

package careercup;

public class removeString {

private int index= 0;

public void removeStrings(String src, String remove){
int len = remove.length();

String finalString = new String();

String getString = src.substring(index,index+len);

while(index+len < src.length()){
getString = src.substring(index,index+len);
if(!(remove.equals(getString))){
finalString += getString;
}
index++;
}

System.out.println(finalString);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

removeString obj = new removeString();

obj.removeStrings("abctheabcthabcthetheabc", "the");

}

}

Oops! corrected code below

package careercup;

public class removeString {

private int index= 0;

public void removeStrings(String src, String remove){
int len = remove.length();
int i = 0;
String finalString = new String();

String getString = src.substring(index,index+len);
while(index+len < src.length()){
//int i = 0;
getString = src.substring(index,index+len);
if(!(remove.equals(getString))){
if(i%3==0)
finalString += getString;
else
;
}
index++;i++;
}

System.out.println(finalString);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

removeString obj = new removeString();

obj.removeStrings("abctheabcthabcthetheabc", "the");

}

}

Pattern (Java)

Get the integer equivalent of the input2 using atoi function.
Count the number of characters in the input2.
Start parsing input1. Stride input1 by a value equal to strlen(input2), lets call this a chunk. If integer value of the chunk is equal to integer value of input2, then don't copy the chunk into output string. Else copy chunk into output string. I suppose this would improve the running time. Please comment.

We can use the API's provided by Java. This will be the most efficient method.

package google;

public class RemoveInput2FromInput1 {

private String a,b;

public RemoveInput2FromInput1(String a, String b) {
// TODO Auto-generated constructor stub

this.a = a;
this.b = b;

assert(!this.a.equals(null));
assert(!this.b.equals(null));
}

private void removeExp(){
String out = a.replaceAll(b,"");
assert(!out.equals(null));
System.out.println(out);
assert(out.equals("abcthabdshhtexyzaaa"));
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
RemoveInput2FromInput1 obj = new RemoveInput2FromInput1("abcthabdtheshhtexyztheaaa","the");
obj.removeExp();
}

}

I think it can be done in linear time. Just consider it a pattern recognition and you can use automaton to do all the tricks.

Almost the same as this one:
http://www.careercup.com/question?id=62468

I can only figure out a O(N*M) solution:

#include<string>
#include<iostream>
using namespace std;

void main(){
const string input1="abcthabdtheshhtexyztheaaa";
const string input2="the";
if(!input2.size() || input1.size()<input2.size()){
cout<<input1;
return;
}
char c=input2.at(0);
for(string::size_type i=0; i<input1.size(); ){
if(input1.at(i) != c || i>=input1.size()-input2.size()+1){
cout<<input1.at(i);
i++;
}
else{
if(!input2.compare(input1.substr(i,input2.size())))
i=i+input2.size();
else
i++;
}
}
}

private string RemoveSubString(String src, String remove)
{
int index = 0;
StringBuilder finalString = new StringBuilder();
int len = remove.Length;

while (index < src.Length)
{
if (src[index] == remove[0])
{
String subString = src.Substring(index, len);
if (subString.Equals(remove))
{
index += len;
}
else
{
finalString.Append(src[index]);
index++;
}
}
else
{
finalString.Append(src[index]);
index++;
}
}
return finalString.ToString();
}