This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Solution Notebook

Problem: Implement an algorithm to determine if a string has all unique characters

Constraints
Test Cases
Algorithm 1: Sets and Length Comparison
Code: Sets and Length Comparison
Algorithm 2: Hash Map Lookup
Code: Hash Map Lookup
Algorithm 3: In-Place
Code: In-Place
Unit Test

Constraints

Can you assume the string is ASCII?
- Yes
- Note: Unicode strings could require special handling depending on your language
Can we assume this is case sensitive?
- Yes
Can you use additional data structures?
- Yes

Test Cases

'' -> True
'foo' -> False
'bar' -> True

Algorithm 1: Sets and Length Comparison

A set is an unordered collection of unique elements.

If the length of the set(string) equals the length of the string
- Return True
Else
- Return False

Complexity:

Time: O(n)
Space: Additional O(n)

Code: Sets and Length Comparison



In [1]:

    
def unique_chars(string):
    return len(set(string)) == len(string)

Algorithm 2: Hash Map Lookup

We'll keep a hash map (set) to keep track of unique characters we encounter.

Steps:

Scan each character
For each character:
- If the character does not exist in a hash map, add the character to a hash map
- Else, return False
Return True

Notes:

We could also use a dictionary, but it seems more logical to use a set as it does not contain duplicate elements
Since the characters are in ASCII, we could potentially use an array of size 128 (or 256 for extended ASCII)

Complexity:

Time: O(n)
Space: Additional O(n)

Code: Hash Map Lookup



In [2]:

    
def unique_chars_hash(string):
    chars_set = set()
    for char in string:
        if char in chars_set:
            return False
        else:
            chars_set.add(char)
    return True

Algorithm 3: In-Place

Assume we cannot use additional data structures, which will eliminate the fast lookup O(1) time provided by our hash map.

Scan each character
For each character:
- Scan all [other] characters in the array
  - Exluding the current character from the scan is rather tricky in Python and results in a non-Pythonic solution
  - If there is a match, return False
Return True

Algorithm Complexity:

Time: O(n^2)
Space: O(1)

Code: In-Place



In [3]:

    
def unique_chars_inplace(string):
    for char in string:
        if string.count(char) > 1:
            return False
    return True

Unit Test



In [4]:

    
%%writefile test_unique_chars.py
from nose.tools import assert_equal


class TestUniqueChars(object):

    def test_unique_chars(self, func):
        assert_equal(func(''), True)
        assert_equal(func('foo'), False)
        assert_equal(func('bar'), True)
        print('Success: test_unique_chars')


def main():
    test = TestUniqueChars()
    test.test_unique_chars(unique_chars)
    try:
        test.test_unique_chars(unique_chars_hash)
        test.test_unique_chars(unique_chars_inplace)
    except NameError:
        # Alternate solutions are only defined
        # in the solutions file
        pass


if __name__ == '__main__':
    main()









    



Overwriting test_unique_chars.py



In [5]:

    
%run -i test_unique_chars.py









    



Success: test_unique_chars
Success: test_unique_chars
Success: test_unique_chars