quick and dirty beautiful finder

beautiful_iterative.rb

#s = "ABCDEFABDC".split("")
s = "nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle".split("")
ans = 'tsocrpkijgdqnbafhmle'
#s = "CABDBACBAB".split("")
#ans = "DCBA"

h = {}.tap do |h|
  s.each_with_index do |c,i|
    h[c] ||= []
    h[c] << i
  end
end

most_beautiful_string = ""

left_bound = right_bound = -1
while h.any?

  right_bound = h.map do |char, positions|
    positions.select{|p| p >= left_bound}.max
  end.min

  candidates = left_bound.upto(right_bound).map(&:to_i)
  
  next_char = h.select do |char, positions|
    (positions & candidates).any?
  end.map(&:first).flatten.max

  most_beautiful_string << next_char

  left_bound = h[next_char].select{|i|i<=right_bound}.max
  
  h.delete(next_char)
end                 

puts most_beautiful_string
puts most_beautiful_string == ans