1.1 Is Unique – CCI

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

Part 1

  • Create a hash table that keeps track of count for each character
  • Loop through each character and add to hash table if not already in there
  • If character is in the hash table, there must be a duplicate
# Time complexity: O(n) because needs to check each character
# Space complexity: O(c) where c is each character

import unittest

def is_unique(s):
    # create a hashmap to keep track of char count
    char_count = {}

    for char in s:
        # if character is not in hashmap add it
        if not char in char_count:
            char_count[char] = 1
        else:
            # if char is in hashmap, means there is a duplicate character
            return False

    return True


class Test(unittest.TestCase):
    
    def test_unique(self):
        self.assertTrue(is_unique('abcdefg'))
        self.assertTrue(is_unique('1234567'))
        self.assertFalse(is_unique('aabcdefg'))
        self.assertFalse(is_unique('123456788'))


if __name__ == "__main__":
    unittest.main()

Part 2: No Additional Data Structures

  • Loop through each character
  • for each character loop through all characters
  • make sure you are not comparing the same character
  • otherwise, if the characters are equal, not all characters are unique
# Time complexity: O(n**2) because loops through all characters for each character
# Space complexity: O(1)

import unittest

def is_unique(s):
    
    for i, char1 in enumerate(s):
        for j, char2 in enumerate(s):
            if i != j and char1 == char2:
                return False

    return True


class Test(unittest.TestCase):
    
    def test_unique(self):
        self.assertTrue(is_unique('abcdefg'))
        self.assertTrue(is_unique('1234567'))
        self.assertFalse(is_unique('aabcdefg'))
        self.assertFalse(is_unique('123456788'))


if __name__ == "__main__":
    unittest.main()