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?
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.
Reply
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.
Reply
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/
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;
}
You need to login/register to answer the question. Or connect with