Remove duplicate characters from a string without using additional buffer

Question

I am working on an interview question where I need to remove duplicate characters from the String without using additional buffer.

Below is the code I have but it's not giving right output for this string "aabbab". Is there anything wrong in below code?

  private static void removeDuplicates(char[] str) {
    if (str == null)
      return;
    int len = str.length;
    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;
  }

I am not able to figure out what is wrong in the above code after debugging.

`if (str[i] == str[j]) break;` It looks like when you find a dupe you just `break` — GBlodgett, Nov 02 '18 at 02:32
Possible duplicate of [Finding duplicates in O(n) time and O(1) space](https://stackoverflow.com/questions/5739024/finding-duplicates-in-on-time-and-o1-space) — jrook, Nov 02 '18 at 02:55
Instead of iterating each character to remove duplicate string. you can use regular expression. — Aravind P, Nov 02 '18 at 06:50

score 0 · Answer 1 · answered Nov 02 '18 at 02:53

It needs to do like this

if (str == null)
        return;
int len = str.length;
if (len < 2)
    return;
for(int i = 0; i <len; i++) {
    for(int j = i+1; j<len; j++) {
        if(str[i] == str[j]) {
            str[j] = 0;
        }
    }
}

But the result will look like this a[space]b[space][space][space] because we just set the character to 0.

score 0 · Answer 2 · answered Nov 02 '18 at 04:00

This question's time complexity is O(n^2).

But if your input char array has some restrict， such as char array is between 'a' and 'z'. It has O(n) method to solve.

The idea of that is use bits of one variable to save charactor appeared.

void removeDuplicate(char s[])
{
    int len = strlen(s);
    if(len < 2) return;
    int check = 0, p = 0;
    for(int i=0; i < len; ++i)
    {
        int v = (int)(s[i]-'a');
        if((check & (1 << v))==0)
        {
            s[p++] = s[i];
            check |= (1 << v);
        }
    }
    s[p] = '\0';
}

ps. This code is from other website.

score 0 · Answer 3 · answered Nov 02 '18 at 04:07

So basically we will mark the duplicates first with some special characters and then we need to remove those special characters. Time complexity would be O(n^2).

char[] str = "aabbabcdcd".toCharArray();
        int len = str.length;
        if (len < 2)
          return;

Step-1, Mark the positions with some special characters like 0 or $

for (int i = 0; i < len-1; ++i) {
            for(int j=i+1;j<len;j++)
            {
                if(str[i]==str[j])
                {
                    str[j]=0; //<---mark the positions      
                }
            }
        }

Output: a b cd

Step-2, We need to remove those inner black space

int j;


for(int i=1;i<len-1;i++)
{
  if(str[i]==0)
  {
      for(j=i+1;j<len;j++)
      {
          if(str[j]!=0)
          {
              break;  
          }
      }
      if(j!=len)  //<-----replace with blank
      {
        str[i] = str[j];  
        str[j]=0;  
      }

  }


}

Output: abcd

Remove duplicate characters from a string without using additional buffer

3 Answers3