I assume you mean first non-repeated character. Anyways heres a possible performance improvement for a very long string: Assume the string is stored as a link

I assume you mean first non-repeated character. Anyways heres a possible performance improvement for a very long string: Assume the string is stored as a linked-list (so removing characters from the middle of the string is cheap). Then remove duplicates from the string during the initial traversal (keep track of unique characters that were removed as duplicates in a hashtable). After this single traversal the character in the head node of the remaining linked-list will be the first non-repeated character in the original string. Note the string must be stored in the linked-list initially... if we're responsible for moving the string from a theoretical array w/ billions of elements then we have to traverse the string twice just like the original algorithm and nothing is gained. Please clarify the "usually in the middle" part of your question. In this case do we always have to return the first non-repeated character? Or can we just be close?