Cracking the iOS Interview: Array Questions #1 - Is Unique

Cracking the iOS Interview: Array Questions #1 - Is Unique

Swift solutions to questions from Cracking the Coding Interview and other sources

Is Unique: Implement an algorithm to determine if a string has all unique characters.

The following is a Swift solution to question 1.1 in Cracking the Coding Interview

1 - Normal person approach (non-engineer)

I would probably write down on a piece of paper each character that I saw, one by one. But with each new character I would go through the characters I had previously written down to see if it matched any of them. If it did, I would say it does not have all unique characters. If there isn't a matching character then I add it to the list. If I get to the end of the string without finding a duplicate, then the string has all unique characters.

2 - Code translation

The above sounds like I made a dictionary on paper. So if I go through the string, character by character, and add each character to the dictionary as a key with a default value of true, this will make it super easy for lookups. Dictionary lookups are O(1). I look up the value using the key and if it even exists, then that means that character was already seen in the string. So we just return false right there. It honestly doesn't really matter what the value part is in the [key: value] dictionary, all we care about is that the key is there and we use the dictionary for that lookup speed. Let's code this up.

func isUnique(s: String) -> Bool {
    // If the string has a length of 0 or 1, then it will never have
    // duplicates so we can return true right from the guard
    guard s.count > 1 else {
        return true
    }

    var charDict = [Character: Bool]()
    for char in s {
        guard charDict[char] == nil else {
            return false
        }

        charDict[char] = true
    }

    return true
}

Looks pretty good. Runs in O(n) time, since we need to touch every character in the string once. In this case it would take up O(1) space if we are assuming that it is a fixed character set, such as all letters in the English alphabet. If the valid character set could be variable, then we could say it takes up O(c) space where c is the character set length.

3 - Another way

Another way that we could do this is by using a Swift Set. A Set doesn't allow duplicates and can be converted from an array. So if we first take the length of the string, then convert the string to an array, and then convert that to a set and compare the length of the set to the string's original length, we should be able to tell right there whether or not there is a duplicate. If the lengths are the same, the string has unique characters. If the length is different (the set is shorter), then the string is not made up of unique characters since that means one or more duplicate characters was removed in the set. Let's code this.

func isUnique(s: String) -> Bool {
    // If the string has a length of 0 or 1, then it will never have
    // duplicates so we can return true right from the guard
    guard s.count > 1 else {
        return true
    }

    let originalCount = s.count
    let sArray = Array(s)
    let sSet = Set(sArray)

    return originalCount == sSet.count
}

Now to convert the array to a set is still going to require touching each character in the array, so the time complexity is still O(n). Even though we are also creating a couple of different data structures, the space situation remains the same as the dictionary, O(1) space if we are assuming that it is a fixed character set and if the valid character set could be variable, then O(c) space. It doesn't improve anything over the previous approach, but it is a different way of doing things that is a little bit simpler in my opinion.

4 - Without additional data structures?

How could we do this without using any of these additional data structures, like a dictionary or a set? Well, with no way to keep track of all our characters, we'd have to take each character in the string, and then knowing that character, go through the entire string to see if another character matches it. We'd probably want to keep track of the index so we don't count the same character as a duplicate. So this is going to be a loop with a loop inside of it. Let's code it.

func isUnique(s: String) -> Bool {
    // If the string has a length of 0 or 1, then it will never have
    // duplicates so we can return true right from the guard
    guard s.count > 1 else {
        return true
    }

    for (i, char) in s.enumerated() {
        for (j, secondChar) in s.enumerated() {
            guard i != j else {
                continue
            }
            guard char != secondChar else {
                return false
            }
        }
    }

    return true
}

This is going to be much slower. A for loop within a for loop like this will result in exponential time, O(n2). We still use constant space O(1) though. If we absolutely cannot use any additional data structures, then perhaps this is the solution to use.

Fim

Well, we made through the first question of the book. Not too complex, but there are some interesting ways to solve it. Feel free to comment with any suggestions or questions about anything, both how I solved these problems as well as general Swift questions.