shaunhyp57

''' 
Cracking The Coding Interview: 
Ch 1 Arrays and Strings: 
Q1 - Is Unique
"Implement an algorithm to determine if a string has all unique characters. 
What if you cannot use additional data structures?"

Solutions:      Time Complexity:
Brute Force     O(n^2)
Dictionary      O(n)

shaunhyp57

def no_ds_is_unique(input_string):
    letters = 'abcdefghijklmnopqrstuvwxyz'

    for c in input_string:
        if c in letters:
            letters = letters.replace(c, "")
        else:
            return False
    return True

shaunhyp57

def set_is_unique(input_string):
    if len(set(input_string)) == len(input_string):
        return True
    return False

shaunhyp57

# using dictionary
# complexity:
# time - O(n)
# space - O(n)

def dict_is_unique(input_string):
    unique = {}

    for c in input_string:
        if c in unique:

shaunhyp57

# naive solution
# complexity:
# time - O(n^2)
# space - O(1)

def naive_is_unique(input_string):
    length = len(input_string)

    if length < 2:
        return True