Jul 022012

Given a string of characters. Write code which will remove duplicate characters from the string:

Input: "social.ritambhara.in"
Output: "social.rtmbhn"


There can be multiple solutions to this problem each having its own benefits and limitations. lets see some of the ways of removing the duplicates:

Method-1: Bruite-Force Method (Remove if the character is already present before in the string)

For each character 
 - check wither this character is seen earlier in the string or not 
    - If Yes, remove the character (duplicate)


I have not written the code to sort the string (Use quick sort, because the string is of random characters)

    /** Function to remove the duplicate characters from the given string 
    void removeDuplicates(char* str)
        if(str == NULL || str[0] == '\0' || str[1] == '\0')

        for(int i=1; str[i]!= '\0'; i++)
            bool dup = false;
            for(int j=0; j<i; j++)
                if(str[j] == str[i])
                    dup = true;

            if(dup)    // Duplicate. Remove the char
                for(int j=i; str[j] != '\0'; j++)
                    str[j] = str[j+1];

                // This is important, else one character will be skipped

Time Complexity: In the worst case this algorithm will take O(n2) time
Extra Space:     Constant….  O(1)

Obviously this is not a good method. Lets move ahead and discuss better methods:

Next: Method-2: Using Sorting

  2 Responses to “Remove duplicates from a string”

Comments (2)
  1. where is n in array?

 Leave a Reply

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=""> <s> <strike> <strong>