first-non-repeating-character.rb

# algorithm for finding first non repeating character
# should be faster than using a O(n^2) nested for loop

class Fnrc

  def self.find_fnrc string
    characters = Hash.new
    position = 0

    # O(n)
    string.each_char do |c|
      if characters[c].nil?
        characters[c] = {character: c, count: 1, position: position}
      else
        characters[c][:count] += 1
      end
      position += 1
    end

    # O(n)
    characters.select! do |k, v|
      v[:count] == 1
    end

    # O(nlogn)
    characters = characters.to_a.sort_by do |c|
      [c[1][:position]]
    end

    # O(1)
    if characters.first.nil?
      nil
    else
      characters.first[1]
    end
  end
end

puts Fnrc.find_fnrc 'aaabbTddeee ff g' # should return T

puts Fnrc.find_fnrc 'aaa bbb ccc ddd L eee fff ggg' # should return L

puts Fnrc.find_fnrc 'aaa bbb ccc' # should return nil