Test if string has all unique characters

Here comes another typical question from coding interviews: "Test whether all characters within a string are unique". An inefficient solution with O(n^2) complexity is to loop over all characters of the string and test in a second, inner loop whether an equal character can be found:

  
def all_unique(str):
    for ch1 in str:
        for ch2 in str:
            if ch1==ch2:
                 return False
    return True 

This is obviously not what the interviewer is after. A simple and efficient solution is to convert the string to a set of characters and to compare the number of elements in the set with the length of the string:

 
def all_unique(str): 
    return len(set(str)) == len(str)   

Too easy and therefore the interviewer doesn't like it either ;-). What is wanted is a mapping of characters to a boolean/bit array that indicates which character has been found in the string so far:

  
def all_unique(str):
    test = [False]*256
    for ch in str:
        idx = ord(ch)
        if test[idx]: return False
        test[idx] = True
    return True 

This approach has linear time complexity but requires an array with the length of the size of the character set.