For each non-empty prefix of a given string consisting of lowercase English letters, find the first non-repeated character if any.
Input. The input file consists of one or more input strings, one per line and is terminated by an EOF character. Consider the following example.
Output. The output file consists the count of unique non-empty substrings for each input string. The following example corresponds to the previous example input.
For each prefix of a given input string, we determine the first non-repeated letter by determining the repeated letters and picking the first that is not repeated.
For example, consider the prefixes of input string “ababc”.
For prefix “a”, there are no repeated letters and thus we pick letter “a”. We also remember that “a” has appeared for the first time. We remember the first non-repeated letter by placing a token on top of the first position of “ababc” like so.
For prefix “ab”, we figure that “b” appears for the first time and remember that. Also, the first non-repeated letter is still “a” because “a” is not repeated and the token we put is still on the first position of “ababc”.
For prefix “aba”, we know that “a” is repeated because we had already found it before, so we remember that “a” is repeated. Also, we figure that the first non-repeated letter is “b” because given that “a” is repeated we move the token to the right and arrive to “b” which is not repeated, like so.
For prefix “abab”, we figure that “b” is repeated and remember that. This time all letters are repeated because we move the token to the right beyond the fourth position without finding a letter that is not repeated, like so.
You can remember how many times you have found a given letter by using a hash or an array with enough capacity.
Here is a Ruby implementation.
Want to read more?
I regularly write solutions to programming problems that you may or may not find in technical job interviews. I also love to explain those solutions and answer questions. If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.