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.

  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);

    }

    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation