An answer to this question on Stack Overflow.

Question

The problem asks to "implement an algorithm to determine if a string has all unique character.

I saw the solution, but don't quite understand.

public boolean isUniqueChars(String str) {
    if (str.length() > 256) return false;
    boolean[] char_set = new boolean[256];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (char_set[val])
            return false;
        char_set[val] = true;
    }
    return true;
}

Do we not use parseInt or (int) converter in front of the code? (Will str.charAt[i] be automatically changed to int?) What does boolean[] char set=new boolean[256] mean? Why do we need to set char_set[val]=true?

Answer

Think about how you would do this with a paper and pencil.

Write out the alphabet once.

Then go through your string character by character.

When you reach a character cross it out of your alphabet.

If you go to cross out a character and find that it has already been crossed out, then you know the character appeared previously in your string and you can then stop.

That's essentially what the code you posted does, using an array. The operation completes in O(N) time with O(K) extra space (where K is the number of keys you have).

If your input had a large number of elements or you could not know what they were ahead of time, you could use a hash table to keep track of which elements have already been seen. This again takes O(N) time with O(cK) extra space, where K is the number of keys and c is some value greater than 1.

But hash tables can take up quite a bit of space. There's another way to do this. Sort your array, which will take O(N log N) time but which requires no extra space. Then walk through the array checking to see if any two neighbouring characters are the same. If so, you have a duplicate.