Programming Interviews Exposed: Secrets to Landing Your Next Job, Second Edition

6.3. Array and String Problems

Many string problems involve operations that require converting the string to an array and back for efficient processing of the string.

6.3.1. Find the First Nonrepeated Character

NOTE

Write an efficient function to find the first nonrepeated character in a string. For instance, the first nonrepeated character in "total" is 'o' and the first nonrepeated character in "teeter" is 'r'. Discuss the efficiency of your algorithm.

At first, this task seems almost trivial. If a character is repeated, it must appear in at least two places in the string. Therefore, you can determine whether a particular character is repeated by comparing it with all other characters in the string. It's a simple matter to perform this search for each character in the string, starting with the first. When you find a character that has no match elsewhere in the string you've found the first nonrepeated character.

What's the time order of this solution? If the string is n characters long, then in the worst case you'll make almost n comparisons for each of the n characters. That gives worst case O(n²) for this algorithm. You are unlikely to encounter the worst case for single-word strings, but for longer strings, such as a paragraph of text, it's likely that most characters would be repeated, and the most common case might be close to the worst case. The ease with which you arrived at this solution suggests that there are better alternatives — if the answer were truly this trivial, ...