# Remove duplicate characters in a string

Given a string, Write a program to remove duplcate characters from the string.

Input String : crazyforcode

Output String : crazyfode

Algorithm :

1. For each character, check if it is duplicate of already found characters.
2. Skip duplicate characters and update the non duplicate characters.

Method 1 Using Extra Space.

```void removeDuplicates(char *str)
{

if (!str)
return;
int len = strlen(str);
if (len < 2)
return;
bool hit[256];
for(int i = 0; i < 256; ++i)
hit[i] = false;

hit[str[0]] = true;
int tail = 1;
for (int i = 1; i < len; ++i)
{
if (!hit[str[i]])
{
str[tail] = str[i];
++tail;
hit[str[i]] = true;
}
}
str[tail] = '\0';
}
```

Time Complexity : O(N)

Method 2 : Without using extra space.

```void removeDuplicates(char *str)
{
if (!str)
return;
int len = strlen(str);
if (len < 2)
return;

int tail = 1;
for (int i = 1; i < len; ++i)
{
int j;
for (j = 0; j < tail; ++j)
if (str[i] == str[j])
break;

if (j == tail)
{
str[tail] = str[i];
++tail;
}
}
str[tail] = '\0';
}
```

Time Complexity : O(N^2)

### 7 Thoughts on “Remove duplicate characters in a string”

1. Amit Jain on July 14, 2013 at 11:50 pm said:

bool hit[256];
for(int i = 0; i < 256; ++i)
hit[i] = false;

Instead of above code just nelow will work

bool hit[256] = {0} ;

2. crazyadmin on July 15, 2013 at 9:44 am said:

Yes Amit. Your code would just work fine. Used for loop to make it more clear.

3. mhassan83 on August 24, 2013 at 4:29 pm said:

This can be done in O(nlogn).

First sort the array using quick sort.
Than compare each char with next char until repeated.

• crazyadmin on August 24, 2013 at 4:47 pm said:

Yes.It can be done in O(nlogn) but after sorting order of characters won’t remain same.

4. Kinshuk on April 26, 2014 at 12:14 am said:

if characters lies in the range a…z, then we can use following O(n) method without using extra space :

public static void removeDuplicates(char[] str) {
int map = 0;
for (int i = 0; i < str.length; i++) {
if ((map & (1 < 0) // duplicate detected
str[i] = 0;
else // add unique char as a bit ’1′ to the map
map |= 1 << (str[i] – 'a');
}
}

(borrowed from kodeknight)

5. I think the second method with complexity O(n ^ 2) can remove consecutive duplicates. for example it can convert abcdddefgg to abcdefg but it can not convert abcdefab to abcdef though the first one would do it.

have you given it a thought ??

6. Tarun on June 27, 2015 at 7:27 pm said:

public class Anagram {
public static void main(String[] args) {
String s1=”asdfas” ;
char [] arr=new char[256];
System.out.println();
for(int i=0;i<s1.length();i++)
{
arr[s1.charAt(i)]++;
}
for(int i=0;i1)
arr[i]–;
if(arr[i] == 1)
System.out.printf(“%c”,i);

}

}
}