Remove the duplicate characters in a string

Question

This is from cracking the Coding Interview Book.

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.

In the book it says time complexity is $O(N^2)$. How can we tell that the time complexity is $O(N^2)$ from the solution? I have questions as to how the solution is removing duplicate characters. I have included them in the inline comments below.

   public static void removeDuplicates(char[] str) {
      if (str == null) return; // if the array is empty return  nothing?
      int len = str.length; // get the length of the array 
      if (len < 2) return; // if the array length is only 1 return nothing?
      int tail = 1; // initialise tail variable as 1 ! 
      // Why are we starting at second character here (at i = 1),why not start at i = 0 ? 
      for (int i = 1; i < len; ++i) { 
        int j;

        for (j = 0; j < tail; ++j) { // so are we checking if j is less then 1 as tail has been initialized to 1 
          if (str[i] == str[j]) break; // stop, if we find duplicate.
        }

        if (j == tail) { why are we comparing j to tail(1) here ?
          str[tail] = str[i]; // assigning the value 
          ++tail; // incrementing tail
        }
      }
      str[tail] = 0; //setting last element as 0 
    }


 - 

Answer 1

I completly rely on @pbabcdefp comment as I'm to lazy to test it, but it seems like your algorithm does not work.

I did not like it anyway, here how I would do it with explanation in comments :

public static void main(String[] args) {
    removeDuplicates(new char[]{'a','a','b','b','c','d','c'});
}

public static final void removeDuplicates(char[] str)
{
    /*
     * If the str is not instantiated, or there is maximum 1 char there is no need to remove duplicates as 
     * it is just impossible to have duplicate with 1 char.
    */
    if (str == null || str.length < 2)
        return;

    //loop over each char
    for(int i = 0; i < str.length; i++)
    {
        //no need to check with earlier character as they were already checked, so we start at i + 1
        for(int j = i + 1; j < str.length; j++)
        {
            //if they match we clear
             if(str[j] == str[i])
                str[j] = ' ';
        }
    }

    System.out.println(str);
}

That would output a b cd.