Is Unique

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Solution 1

One way to solve this problem is to sort the array, and to iterate through each element of the array. If there are duplicate elements, they will be adjacent.

def is_unique(input_str):
    chars = list(input_str)
    chars.sort()

    y = None

    for x in chars:
        if(x == y):
            return False

        y = x

    return True

This solution has two steps. First, the array is sorted which takes \(O(n \ log \ n)\) time. Second, the array is iterated over which takes time \(O(n)\). In total the algorithm has a time complexity of

Solution 2

We can do better. Let’s create a supplemental data structure, to represent each character in the alphabet. For example, if the string is an ASCII string we will instantiate an array 128 elements long. We then iterate through the array, and when we encounter one of the letters we will increment that element of the array.

def solution_2(input_string):
    char_set = [0] * 128

    for x in input_string:
        i = ord(x)

        if(char_set[i] > 0):
            return False
        else:
            char_set[i] += 1

    return True

Notice this solution has time complexity, \(O(n)\). The only operation on the array is an iteration over the array, one time.