Chapter 1 Arrays and Strings - 1.1

This the first problem in the "Cracking the Coding Interview" book. The statement of problem is presented below:

1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structure?

The time complexity of my first solution is O(nlgn). It iterates all characters in the given string and employs a map to record the characters that have been seen so far. I considered the hash table and naively thought it is the same as map. Later I found that I couldn't be more wrong. For a map the lookup cost is O(lgn), while it costs O(1) for a hash tabel to lookup a value with given key (if the hash table is big enough).

The standard answer is:

If the characters only come from ASCII table, we can create a lookup table whose size is 256 and use it to indicate whether a character has been seen before. The Python code is given below:

def allUnique(str):
    flags = [False for i in range(0, 255)]
    for i in range(0, len(str)):
        charCode = ord(str[i])
        if flags[charCode] == False:
            flags[charCode] = True
        else:
            return False
    return True
           

If characters in the given string come from a wider character set, we can just enlarge the hash table.

This solution reminds me that I should figure out (or assume) the reasonable limit of input to optimize the algorithm. We need code that can work in real work, not ideal one.

Then, how to solve it without help of any additional data structure?

The brute force method costs O(n^2). I came up with a method, which sorts the string first with quick sort (in place). Then we can just iterate each character and look for it with binary search in the string (how stupid!), which turns out cost O(nlgn).

Then I turned to the standard answer and found that sorting is a good choice, however, after sorting we can just linearly compare each pair of neighbors to check the duplication. The time complexity of standard answer is O(nlgn). The implementation is given below:

def quickSort(str, left, right):
    if left >= right:
        return
    pivotIdx = left
    pivot = str[left]
    for i in range(left+1, right+1):
        if pivot >= str[i]:
            str[pivotIdx+1], str[i] = str[i], str[pivotIdx+1]
            pivotIdx += 1
    # Swap the two elements
    str[left], str[pivotIdx] = str[pivotIdx], str[left]
    quickSort(str, left, pivotIdx-1)
    quickSort(str, pivotIdx+1, right)

def allUnique(str):
    strSeq = [i for i in str]
    quickSort(strSeq, 0, len(str)-1)
    for i in range(0, len(strSeq)-1):
        if(strSeq[i] == strSeq[i+1]):
            return False
    return True
           

One thing to mention is that it is the third time I try to implement a quick sort. However, I failed again. I always make the same mistake: not keeping the record of pivot value and use pivotIdx to get the pivot. Remember that pivotIdx is moving and you should keep a copy of pivot value.