Constant Time implementation of String Uniqueness Algorithm I've written what I think is a constant time implementation of a uniqueness check. I've seen many algorithms online, which run in linear time, but was wondering whether my conclusion that this runs in constant time was correct.

I've seen many linear versions of this algorithm, but I haven't seen any that run in O(1).

Any feedback on style, flaws in the code, or how to improve the algorithm would be greatly appreciated.

from string import printable 


def is_unique(string):
    """Checks whether a string is unique or not.

    Big O:

      O(S * C) - Constant Time

      Where:

        `S` is the characters of the string being checked for uniqueness
        `C` is a set of all ASCII characters (not including the extended set)

    """
    if len(string) == 1:
        # A single character is always going to be unique
        return True

    if len(string) &gt; len(printable):
        # If there are more characters than the ASCII character set, 
        # then we know there are duplicates
        return False

    found_character = bytearray(len(printable))

    for character in string:
        for index, ascii_value in enumerate(printable):
            if character == ascii_value:
                if found_character[index] == True:
                    return False

                # Set the index of the ASCII value in our bytearray to True
                found_character[index] = 1
                break

    return True


is_unique(string='abc')
Critique

You have to describe something for which your input scale, which in this would be the length of your string, so in this regard your implementation is still linear. The part where you try every single possible index for storing a specific character is overkill, since it is often possible to directly calculate it through some kind of hashing. It would therefore be much faster to use a dictionary or the equivalent.

Alternative

We can solve this problem very simply for a more general case (any sequence of items is unique) by turning it into a set:

is_unique = lambda xs: len(xs) == len(set(xs))


Note that you might want to do some extra work if you want to only have printable characters, such as by applying a filter first.