Let us a have a string "abbashbhqa". We have to remove the duplicate characters in such a manner that the output should be "abshq". One possible solution is to check each character with the others present in the string and then manipulate. But this requires O(n^2) time complexity. Is there any optimised approach to do so ?
7
-
1Add to a look-up table (this will discard repeats), keep the order. Output in the order of first appearance.user1812457– user18124572016-08-14 10:01:48 +00:00Commented Aug 14, 2016 at 10:01
-
Try to comment before downvoting.Soumya Kanti Naskar– Soumya Kanti Naskar2016-08-14 10:04:46 +00:00Commented Aug 14, 2016 at 10:04
-
@Boris Can you explain what is look up table ?Soumya Kanti Naskar– Soumya Kanti Naskar2016-08-14 10:05:32 +00:00Commented Aug 14, 2016 at 10:05
-
The lookup table can be a short (26 characters in the alphabet) boolean or counter array. Every time you encounter a character, you update the array ( set to true or increment counter).Thilo– Thilo2016-08-14 10:05:35 +00:00Commented Aug 14, 2016 at 10:05
-
Can you look up online what a look-up table is? There are many ways to implement a look-up table, depends on the programming language, facilities, etc. Here is a comment (I didn't downvote): Stackoverflow is not a "give me the codez" free service.user1812457– user18124572016-08-14 10:07:26 +00:00Commented Aug 14, 2016 at 10:07
|
Show 2 more comments
4 Answers
O(n):
Define an array L[26] of booleans. Set all to FALSE. Construct a new empty string
Walk over the string and for each letter check if L [x] is FALSE. If so, append x to the new string and set L [x] to 1.
Copy new string to the old one.
Comments
as soon as you iterate string you create a set (or hash set). in case the alphabet is limited (English letters as in your example) you just can create a 256 boolean array and use ASCII code as a key to it. Make all booleans to be false at starting point. Each iteration you check if array[] is false or true. In case it's false, the symbol is not a duplicate, so you mark it into array[] = true, do not remove from the string and go on. in case it's true - the symbol is a duplicate
Comments
Probably this will be the implementation of the above problem
import java.util.*;
import java.io.*;
public class String_Duplicate_Removal
{
public static String duplicate_removal(String s)
{
if(s.length()<2)
return s;
else if(s.length()==2)
{
if(s.charAt(0)==s.charAt(1))
s = Character.toString(s.charAt(0));
return s;
}
boolean [] arr = new boolean[26];
for(int i=0;i<s.length();i++)
{
if(arr[s.charAt(i)-'a']==false)
arr[s.charAt(i)-'a']=true;
else
{
s= ((new StringBuilder(s)).deleteCharAt(i)).toString();
i--;
}
}
return s;
}
public static void main(String [] args)
{
String s = "abbashbhqa";
System.out.println(duplicate_removal(s));
}
}
answered Aug 15, 2016 at 18:52
Soumya Kanti Naskar
1,0814 gold badges17 silver badges31 bronze badges
Comments
I am solving using Python and it works in O(n) time and O(n) space -- I am using set() as set does not allow duplicates --- In this case the order of elements gets changed -- If u want the order to remain same then u can use OrderedDict() and it also works in O(n) time --
def remove_duplicates(s , ans_set):
for i in s: # O(n)
ans_set.add(i) # O(1)
ans = ''
for char in ans_set:
ans += char
print ans
s = raw_input()
ans_set = set()
remove_duplicates(s , ans_set)
from collections import OrderedDict
def remove_duplicates_maintain_order(a):
ans_dict = OrderedDict()
for i in a: # O(n)
ans_dict[i] = ans_dict.get(i , 0) + 1 # O(1)
ans = ''
for char in ans_dict:
ans += char
print ans
s = raw_input()
remove_duplicates_maintain_order(s)
