String Contains All Unique Characters or Not

Problem:
Given a string, determine if this string contains all unique characters.

Assumption:
The characters in this string are from ASCII character set. In other words, the value range is 0~255.

Solution 1:
Directly compare each character in the string with every other character in the string. This approach will take \(O(n^2)\) time and no space.

Solution 2:
If allowed to destroy the string, we may first sort the string using quicksort, and then scan through the string to see if there are 2 adjacent characters are the same. Quicksort will take \(O(n\log n)\) time and \(O(1)\) space. If using mergesort, it will take \(O(n)\) space. In Java, to sort the string, an extra array or StringBuffer is needed.

Solution 3:
Since the characters are in a small range, and we can create an array to record if one certain character has appeared or not. This approach will take \(O(n)\) time and \(O(m)\) space, where \(m\) is the size of character set.

Solution 4:
Similar to Solution 3, but instead of using an array of boolean values, use a set of bits to record the binary values. In Java, \(256/32=8\) int size bits are needed, which can be implemented as an array of 8 integers, and each integer represents 32 characters. In C++, there is a very convenient structure called bitset, which can be beautifully used here.

Notes:
Since the characters are all from the assumed set, and the set size is known. In this case, the maximum length for a string of all unique characters will be the size of the character set. Therefore, for each of the above programs, we may add the following code.

if( s.length() > 256 ) return false;