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.

a
aa
ab
aab

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.

a
a
ab
ab

Solution

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”.

a
ab
aba
abab
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.

*
ababc

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.

 *
ababc

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.

    *
ababc

You can remember how many times you have found a given letter by using a hash or an array with enough capacity.

Ruby implementation

Here is a Ruby implementation.

def first_non_repeated_prefix s
  return nil if s == ''
  o = ''
  l = 0
  h = {}
  s.chars.each_with_index do |c, i|
    if not h.has_key? c
      h[c] = :not_repeated
    else
      h[c] = :repeated
    end
    while l <= i and h[s[l]] == :repeated
      l += 1
    end
    o += s[l] if l < i or h[s[l]] == :not_repeated
  end
  return o
end

while true
  s = readline.strip rescue break
  puts first_non_repeated_prefix(s)
end

Comments