Remove duplicates from a string

Method-2: Using Sorting

Sort the string
- Compare each character with the previous one
      and remove it if it is same (duplicate).

Original String : social.ritambhara.in
After Sorting     : ..aaaabchiiilmnorrst

Removing the blue characters.

There can be two methods to remove adjacent duplicates,

1. remove one duplicate at a time.

If the input string is “aaaabbccccc” and we are removing the duplicate character ‘a’. Then in the first iteration it will become
“aaabbccccc” (One character removed)
In second iteration it will become
 “aabbccccc”
and so on…

2. Find total number of duplicates and remove them all in one go.

In “aaaabbccccc”. a is repeated 4 times, so 3 duplicates. Hence shift all the characters starting from first ‘b’ 3 positions left.

Final String : .abchilmnorst

The  problem with this approach is that the relative positions of characters in the original string will get changed.

Time complexity: O(n.lg(n)) – Sorting will take O(n.lg(n)) time.
Extra space required: constant.. O(1)

Code:

    /** Function to remove the duplicate characters from the given string
     */
    void removeAdjescentDuplicates(char* str)
    {
        if(str == NULL || str[0] == '\0' || str[1] == '\0')
            return;
        int i=0; // will always point to the first character in the set
        while(str[i]!= '\0')
        {
            int j=i+1;
            while(str[j] != '\0' && str[j] == str[i])
                j++;
            // If end of the string is reached, then stop here.
            if(str[j] == '\0')
            {
                str[i+1] = '\0';
                return;
            }
            // No duplicates
            if(j == i+1)
            {
                i++;
                continue;
            }
            int numDuplicates = j-i-1;
            j = i;
            do
            {
                j++;
                str[j] = str[j+numDuplicates];
            }while(str[j+numDuplicates] != '\0');
            i++;
        }
    }

This method also takes a lot of time. In the next section we discuss a method which will take the least time, but uses some extra memory.

 
Next: Metod-3: Using Hashing