Finding the first non-repeated character of a string in O(n) using a boolean array?

Question

My question is related to this earlier question

Find the first un-repeated character in a string.

In one of my interviews I was asked to write a function to determine the first unique character in a string in time O(n) using as extra space only a boolean array of length n. That is, find the first non repeating letter in a string using only O(n) complexity and a bool array of length n. Can some suggest how to solve it with bool array?

Answer 1

Well, if the size of the character set is constant... Say, for instance, 0-255...

Scan the string looking for character 0.

Then scan the string looking for character 1.

Then scan the string looking for character 2.

...

Finally, scan the string looking for character 255.

This takes 256*n operations which is O(n).

During each scan, if the character is unique, mark its position in the bitmap. At the end return the character at the first marked position. (Or just record the first unique character and its location using k + log(n) bits. Use a hard-coded lookup table or whatever for very small n; otherwise, n bits is generous.)

Although somehow I suspect this is not what the interviewer had in mind.