Given a string as input, remove all chars from the string that appear again. That is, while reading a string if a char has appeared previously it will be removed.
for example:
remove("Hello")="Helo"
remove("World")="World"
remove("Sachin Tendulkar") = "Sachin Tendulkr"
Method 1:(Naive approach)
In the naive approach we just simply apply two loops to find out the duplicate character and remove them. See the algorithm below.
Algorithm :
Implementation :
Time Complexity : O(n*n)
Method 2: (Using Hashing)
Through method 1 time complexity we are getting is O(n*n) which will not be efficient if the string is very long.We can remove the duplicates by using the using the hashing in just O(n) time. See the algorithm below ;
Main idea of algorithm:
We will create an int array len1[] of 256 length initializing to 0 .Now the question is why we have taken the length of array as 256 . Because in java there are 256 character and a string can compromised of any of them and ASCCI value of all the character lie between them. hence every time we find a char then increments the corresponding value to it to 1. Next time we time we traverse the same array we check the value in the len1 corresponding to it. As it 1 ,it means it has already been added ,hence we will not add it again.
Algorithm :
Implementation:
Time Complexity : O(n)
Now if you are done with the concept used in the above program then try to do the following problem :
Given two strings, str1 and str2 as input, remove all chars from str1 that appear in str2. remove("Hello","World")="He" (l and o have been removed from Hello as they appear in World)
Please comment if you find any mistake.
for example:
remove("Hello")="Helo"
remove("World")="World"
remove("Sachin Tendulkar") = "Sachin Tendulkr"
Method 1:(Naive approach)
In the naive approach we just simply apply two loops to find out the duplicate character and remove them. See the algorithm below.
Algorithm :
strNew : new string we are creating after removing the duplicates 1. for i=1 to length_of_string 2. for j=0 to i; if(character_has_been_added_earlier ) then increment i(i++); else add characacter_to_strNew and then i++ and j++ ;
Implementation :
public class RemoveDuplicateChars { static String testcase1 = "aaaabbbbbbb"; public static void main(String args[]){ RemoveDuplicateChars testInstance= new RemoveDuplicateChars(); String result = testInstance.remove(testcase1); System.out.println(result); } // function to remove duplicates character public String remove(String str){ String strNew=""; int len=str.length(); // if string is null then return null string if(len==0) { return strNew; } strNew=strNew+str.charAt(0); int i=1; //removing the duplicate character while(i<len) { int flag=1; for(int j=0;j<i;j++) { if(str.charAt(i)==str.charAt(j) ) { flag=0; } } if(flag==0) { i++; } else { strNew=strNew+str.charAt(i); i++; } } return strNew; } }
Method 2: (Using Hashing)
Through method 1 time complexity we are getting is O(n*n) which will not be efficient if the string is very long.We can remove the duplicates by using the using the hashing in just O(n) time. See the algorithm below ;
Main idea of algorithm:
We will create an int array len1[] of 256 length initializing to 0 .Now the question is why we have taken the length of array as 256 . Because in java there are 256 character and a string can compromised of any of them and ASCCI value of all the character lie between them. hence every time we find a char then increments the corresponding value to it to 1. Next time we time we traverse the same array we check the value in the len1 corresponding to it. As it 1 ,it means it has already been added ,hence we will not add it again.
Algorithm :
strNew : new string we are creating after removing the duplicates 1.for i=0 to length_of_string if(len1[string.charAt(i)==0]) then len1[string.charAt(i)==0] and add the character to strNew else increment i++;
Implementation:
public class RemoveDuplicateChars2 { static String testcase1 = "abbc"; public static void main(String args[]){ RemoveDuplicateChars testInstance= new RemoveDuplicateChars(); String result = testInstance.remove(testcase1); System.out.println(result); } //function to remove duplicate character public String remove(String str){ String strNew=""; int len=str.length(); int len1[]=new int[256]; int i=0; while(i<len) { if(len1[str.charAt(i)]==0) { strNew=strNew+str.charAt(i); ++len1[str.charAt(i)]; i++; } else { i++; } } return strNew; } }
Time Complexity : O(n)
Now if you are done with the concept used in the above program then try to do the following problem :
Given two strings, str1 and str2 as input, remove all chars from str1 that appear in str2. remove("Hello","World")="He" (l and o have been removed from Hello as they appear in World)
Please comment if you find any mistake.
No comments:
Post a Comment