1<<-DOC
 2Note: Write a solution that only iterates over the string once and uses O(1) additional memory, 
 3since this is what you would be asked to do during a real interview.
 4
 5Given a string s, find and return the first instance of a non-repeating character in it.
 6If there is no such character, return '_'.
 7
 8Example
 9
10For s = "abacabad", the output should be
11firstNotRepeatingCharacter(s) = 'c'.
12
13There are 2 non-repeating characters in the string: 'c' and 'd'. 
14Return c since it appears in the string first.
15
16For s = "abacabaabacaba", the output should be
17firstNotRepeatingCharacter(s) = '_'.
18
19There are no characters in this string that do not repeat.
20
21Input/Output
22
23[time limit] 4000ms (rb)
24[input] string s
25
26A string that contains only lowercase English letters.
27
28Guaranteed constraints:
291 ≤ s.length ≤ 105.
30
31[output] char
32
33The first non-repeating character in s, or '_' if there are no characters that do not repeat.
34DOC
35
36describe "first_non_repeating_character" do
37  def first_non_repeating_character(message)
38    chars = message.chars
39    hash = chars.inject(Hash.new(0)) { |memo, char| memo[char] += 1; memo }
40    chars.each do |char|
41      if hash[char] <= 1
42        return char
43      end
44    end
45    "_"
46  end
47
48  [
49    { s: "abacabad", x: "c" },
50    { s: "abacabaabacaba", x: "_" },
51    { s: "z", x: "z" },
52    { s: "bcb", x: "c" },
53    { s: "bcccccccb", x: "_" },
54    { s: "abcdefghijklmnopqrstuvwxyziflskecznslkjfabe", x: "d" },
55    { s: "zzz", x: "_" },
56    { s: "bcccccccccccccyb", x: "y" },
57    { s: "xdnxxlvupzuwgigeqjggosgljuhliybkjpibyatofcjbfxwtalc", x: "d" },
58    { s: "ngrhhqbhnsipkcoqjyviikvxbxyphsnjpdxkhtadltsuxbfbrkof", x: "g" },
59  ].each do |x|
60    it do
61      expect(first_non_repeating_character(x[:s])).to eql(x[:x])
62    end
63  end
64end