String unique characters

Question

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

Answer 1

for each character in the string
  if any subsequent character matches it
    fail
succeed

Answer 2

One possible solution - You could extract the string into an array of characters, sort the array, and then loop over it, checking to see if the next character is equal to the current one.

Answer 3

If you can use a little auxiliary memory, then a small array of bits (indexed by the numerical code of the character) is all you need (if your characters are 4-byte Unicode ones you'll probably want a hashmap instead;-). Start with all bits at 0: scan the string from the start -- each time, you've found a duplicate if the bit corresponding to the current character is already 1 -- otherwise, no duplicates yet, set that bit to 1. This is O(N).

If you can't allocate any extra memory, but can alter the string, sorting the string then doing a pass to check for adjacent duplicates is the best you can do, O(N log N).

If you can't allocate extra memory and cannot alter the string, you need an O(N squared) check where each character is checked vs all the following ones.