how to remove duplicate characters in a string?

Question

I have to implements a function that takes a string as an input and finds the non-duplicate character from this string.

So an an example is if I pass string str = "DHCD" it will return "DHC" or str2 = "KLKLHHMO" it will return "KLHMO"

Answer 1

It will do the job

string removedupes(string s)
{
    string newString = string.Empty;
    List<char> found = new List<char>();
    foreach(char c in s)
    {
       if(found.Contains(c))
          continue;

       newString+=c.ToString();
       found.Add(c);
    }
    return newString;
}

I should note this is criminally inefficient.

I think I was delirious on first revision.

Answer 2

For arbitrary length strings of byte-sized characters (not for wide characters or other encodings), I would use a lookup table, one bit per character (32 bytes for a 256-bit table). Loop through your string, only output characters that don't have their bits turned on, then turn the bit on for that character.

string removedupes(string s)
{
    string t;
    byte[] found = new byte[256];
    foreach(char c in s)
    {
        if(!found[c]) {
            t.Append(c);
            found[c]=1;
        }
    }
    return t;
}

I am not good with C#, so I don't know the right way to use a bitfield instead of a byte array.

If you know that your strings are going to be very short, then other approaches would offer better memory usage and/or speed.

Answer 3

It sounds like homework to me, so I'm just going to describe at a high level.

• Loop over the string, examining each character
• Check if you've seen the character before
  • if you have, remove it from the string
  • if you haven't, note that you've now seen that character

Answer 4

I think this article on .NET perls covers it very well.

-John

Answer 5

A Linq approach:

public static string RemoveDuplicates(string input)
{
    return new string(input.ToCharArray().Distinct().ToArray());
}

Answer 6

char *remove_duplicates(char *str) { char *str1, *str2;

if(!str)
    return str;

str1 = str2 = str;

while(*str2)            
{   
    if(strchr(str, *str2)<str2)
    {
        str2++;
        continue;
    }

    *str1++ = *str2++;      
}
*str1 = '\0';

return  str;

}

Answer 7

char* removeDups(const char* str)
{
 char* new_str = (char*)malloc(256*sizeof(char));
 int i,j,current_pos = 0,len_of_new_str;
 new_str[0]='\0';

 for(i=0;i<strlen(str);i++)
{
 len_of_new_str = strlen(new_str);
for(j=0;j<len_of_new_str && new_str[j]!=str[i];j++)
   ;
  if(j==len_of_new_str)
   {
     new_str[len_of_new_str] = str[i];
     new_str[len_of_new_str+1] = '\0';
   }
}
  return new_str;
}

Hope this helps