# All Unique

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

### Clarification questions

- Do whitespace characters count as valid characters, that is if there are two spaces in the string, will the result be false?
- Does capitalization (or any capital letters) matter?

### Solution 1

*Complexity: *

This solution uses a hash table to store all the characters in the string – if the character already in the table, it returns `false`

**Note:** This solution is based on the assumption that hash table access is constant!

1
2
3
4
5
6
7
8
9

def all_unique(st):
hash = dict()
for el in st:
if hash.get(el, True):
# The character is not found
hash[el] = False
else:
return False
return True

### Solution 2

*Complexity: *

If space is more important, and we don’t care if the original array is modified or not, we can sort the string inplace, and just iterate through it in linear time.

**Note:** The assumption here is that either the string is mutable, or the input is not a string but array of characters.

1
2
3
4
5
6

def all_unique(st):
st.sort() # In-place sort
for idx in range(1, len(st)):
if st[idx] == st[idx - 1]:
return False
return True

### Solution 3

*Complexity: *

If we are not allowed to modify the original array, and the space is more important, we can just compare every character to every other character.

1
2
3
4
5
6

def all_unique(st):
for idx in range(len(st)):
for jdx in range(idx+1, len(st)):
if st[idx] == st[jdx]:
return False
return True