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
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 ...
Get Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.