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 love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?