Jul 022012

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

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

Solution:

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)

Code:

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

        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;
                    break;
                }

            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
                i--;
            }
        }
    }

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

loading comments...
  • Facebook
  • Google+
  • Twitter
  • YouTube