determine if a string has all unique characters?

Question

Can anybody tell me how to implement a program to check a string contains all unique chars ?

Answer 1

If you are talking about an ASCII string:

1. Create an int array [0-255], one for each character index, initialised to zero.

2. Loop through each character in the string and increment the respective array position for that character

3. If the array position already contains a 1, then that character has already been encountered. Result => Not unique.

4. If you reach the end of the string with no occurrence of (3), Result => the string is unique.

Answer 2

Sort the characters in the string using your algorithm of choice (e.g. the builtin qsort function), then scan the string checking for consecutive repeating letters; if you get to the end without finding any, the string contains all unique characters.

An alternative may be using some structure that has one bucket for each character the string may contain, all initialized to zero; you scan the string, incrementing the value of the bucket corresponding to the current character. If you get to increment a bucket that already has a 1 inside it you are sure that your string contains duplicates.

This can work fine with chars and an array (of size UCHAR_MAX+1), but it quickly gets out of hand when you start to deal with wide characters. In such case you would need a hashtable or some other "serious" container.

The best algorithm depends on the length of the strings to examine, the size of each character, the speed of the sorting algorithm and the cost of allocating/using the structure to hold the character frequencies.