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

Array and String Problems

Many array and string problems require the use of additional temporary data structures to achieve the most efficient solution. In some cases, in languages where strings are objects, it may be more efficient to convert the string to an array than to process it directly as a string.

Find the First Nonrepeated Character

PROBLEM 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(n2) for this algorithm. [You can improve this algorithm somewhat by comparing each character with only the characters following it, because it has already been compared with the characters preceding it. This is still O(n2).] You are unlikely ...