X

Removing repeated elements in an array.

Eliminate all duplicate characters from a string array. For Eg: if you pass "BANANAS" to the function, it should return "BANS". The repeated characters must be removed from the array itself without using another temporary array. It should not be an O(n^2) solution.

How can I do this?

Jatin Shridhar Jul 28 '2012 at 03:36AM
0
• Sachin Gupta Jul 28 '2012 at 07:15AM

If you want to do this without any extra space and that too in linear time then there must be some other constraint on the problem, otherwise I don't think it can be done.

• Vikesh Khanna Jul 31 '2012 at 06:19AM

You should be able to solve this in linear time only if you allow the use of a 26-length bitvector to use as a hash table of already encountered characters. The hash table is constant extra memory O(26) and ensures O(n) time for the intended problem.

• Sachin Gupta Jul 31 '2012 at 10:02AM

Maybe you can check out this
http://www.mycareerstack.com/question/237/given-a-string-remove-all-the-duplicate-characters/

2
``````string remove(string a)
{
int len=strlen(&a[0]);
for(int i=1;i<128;i++)
{
int c=0;
for(int j=0;j<len;j++)
{
if(a[j]==i)
{
c++;
if(c>1)
{
a[j]='\0';
}
}
}
}
int j=0;
for(int i=0;i<len;i++)
{
while(a[i]=='\0')
i++;
a[j]=a[i];
j++;
}
for(;j<len;j++)
a[j]=0;
return a;
}
``````
Jaspreet Singh Jul 28 '2012 at 03:36AM