Determine if the characters of a given string are all unique.

Assumptions

We are using ASCII charset, the value of valid characters are from 0 to 255

The given string is not null

Examples

all the characters in "abA+\8" are unique

"abA+\a88" contains duplicate characters

Assumption:

Approach: we could use a bit map. since all valid characters binary representation are from 0 to 255. so we could use int array with size equals 8 to represent all information. if the number exists, the corresponding position would be 1.

public class Solution{
    public boolean allUnique(String word) {
        if (word.length() == 0) {
            return true;
        }
        int[] bit_map = new int[8];
        for (for int i = 0; i < word.length(); i++) {
            int val = (int)word.charAt(i); 
            int index = val / 32;
            int bit_position = val % 32;
            if (bit_map[index] & (1 << bit_position) != 0) {
                return false;
            } else {
                bit_map[index] |= (1 << bit_position); 
            }
        }
        return true;
    }
}