For a given string consisting of lowercase English letters, find the first non-repeated character if any.

After you solve this problem, solve First Non Repeated Character For Each Prefix.

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
b

Solution

We solve the problem by detecting the letters that are repeated and then finding the first that is not.

For example, consider input string ‘aab’. To determine the repeated letters, iterate the string in the following way. At each letter, record the occurrence of the letter the first time you find it and the repetition of the letter every subsequent time you find the letter. You may use a hash or an array with sufficient capacity if you have aversion to hashes. When you are done, iterate the string again and return the first letter that is not repeated.

Ruby implementation

def first_non_repeated s
h = {}
s.chars.each do |c|
if not h.has_key? c
h[c] = :not_repeated
else
h[c] = :repeated
end
end
return s.chars.find { |c| h[c] == :not_repeated }
end

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

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?

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.

Comments