1.1 Check if Unique String

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

You could use a nested for loop, but that would you leave you at O(n^2) running time, which is never desired.

The best algorithm still hasto be O(n) because you must check every character at least once.

My approach is to have a separate boolean array that checks if the letter has been seen before. Use of the ASCII table is perfect here, because we can turn a CHAR into an INT. That INT can be the place in the array where we store our boolean value. For example, the string "aba" in ASCII is "65 66 65," where A=65. Well, if we take an Array[65] = true, when we hit the second "a" and check for Array[65], we can see that Array[65] has already been set true, which means this string has repeated "a."

Psuedocode:

CheckUnique ( string input)
Boolean IsInString[256] // 256 because there are 256 available ASCII characters
Change input to CharArray

FOR I from 0 to input_length
       ascii_number = Get_Ascii_number_of(input[i])
       IF IsInString[ascii_number] == true //this letter has already been set true before!!
             return False
       ELSE //never seen this letter before
             IsInString[ascii_number] = true //so set as true
 END FOR
//if you get here,we never hit the same letter twice
return True

improvements:
Space used can be smaller with you know that you are working with only alphabetical letters, and you can use toUpper or toLower to conserve even more space.