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

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

Solution 1

Complexity: $T = O(n), S = O(n)$

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: $T = O(n\log{n}), S = O(1)$

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: $T = O(n^2), S = O(1)$

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