Remove duplicate characters from a string in-place.

Given a string of length ‘N’ (characters), we aim to remove all the characters which are duplicates in the input string. Let us understand this with the following example.

Input: "earth is a beautiful world."
Output: "earth isbuflwod."

Here, the output gives us the same string by removing all characters which occurs more than once in the input string.

To solve this kind of problem, we follow the same approach as we observed in removing alternate characters in a string in-place. The steps are as follows.

  1. Firstly, we maintain a memory to store 127(maximum number of characters) integers and fills that will take all zeros.
  2. Loop over all the characters in the input string. If the value in the array at ASCII value position is one, then we ignore that character. If the value is zero, then we make the position value as one and copies that character into the current position.
  3. Once we process all over the input string, then we get our output without any duplicate characters init.

Let us see the code for this approach.

void removeDupChars(char inp[], int len)
{
    int dp[MAX_CHARS];
    int cnt = 0;
    memset(dp, 0, MAX_CHARS * sizeof(dp[0]));
    for (int i = 0; i < len; i++)
    {
        if (dp[inp[i]] == 1)
        {
            cnt++;
        }
        else
        {
            dp[inp[i]] = 1;
            inp[i - cnt] = inp[i];
        }
    }
}

This runs with a runtime complexity of O(n) with a constant space (O(1)). Complete code with main function is as follows.

// Output
'earth is a beautiful world.' converts to:earth isbuflwod.

It is all about removing duplicate characters with O(N) complexity and constant space. If you know any better solution, please let our readers know by commenting here below. Happy Learning.