Checking if a string contains all unique characters

Question

I am currently reviewing CTCI(Cracking the Coding Interview)

The question is asking me to implement an algorithm which checks whether the characters in a string are all unique however they do not want me to use any auxillary data structures

My Algorithm is relatively straight forward, Two nested loops one starting at 0(i) and another at 1(i+1)

If the condition finds two characters that are equal then I print duplicate characters have been found.

 public static void checkUnique(String s)
{


    for(int i = 0; i<s.length(); ++i)
    {
        for(int j = i +1; j<s.length(); ++j)
        {
            if(s.charAt(i) == s.charAt(j))
            {
                System.out.println("Duplicates found");
            }
        }
    }


}

My question

1. Is this an optimal algorithm, my second approach was to sort, and find a pair which contains the same characters.
2. Obviously a hashmap would be beneficial here, but questions does not really want me to use it.

I have refactored the code and hopefully now it is correct.

Is there any way of reducing it to an O(N) runtime. What if we keep track of the Unicode code's for each char character. I doubt O(N^2) is the best we can do here.

Answer 1

A way to optimize it would be to return as soon as you have found a duplicate, unless the question specifically asks you to list all duplicates.

You could refactor it to something like that:

public static boolean checkUnique(String s) {
    int len = s.length();
    for (int i = 0; i < len; i++) {
        int c = s.codePointAt(i);
        int next = s.indexOf(c, i + 1);
        if (next > i) {
             return false;
        }
    }
    return true;
}

It isn't more efficient as your solution, but I doubt there is an algorithm that can do it better.

Answer 2

If I were your interviewer, I'd not hire you, because of that piece of code.

The one absolute showstopper is that your method prints to System.out instead of returning a boolean.

Even if no one told you explicitly, from a professional developer we expect that algorithms just compute something and give the results to their callers (by means of a boolean return value), and not write it to the user. But your solution mixes the algorithm with text output.

Otherwise, your solution is okay, given the condition that no additional data structure is to be used (by the way, that's a strange condition, not representative for professional development).