lexical_uniques.rb

def lexical_uniques(str)
  letter_positions = {}
  list = str.split("")
  list.each_index do |index|
    letter = list[index]
    letter_positions[letter] = letter_positions[letter] ? letter_positions[letter] + [index] : [index]
  end


  # iterate through the keys in alphabetical order,
  #
  # for first key, take lowest possible index
  #
  # for the rest of the keys, iterate through its list of possible indices, and:
  #   if current index gives a smaller lexicographical order than the previous index, make this the current index and check the next
  #   if current index gives an identical string to previous, take previous and move to next key

  letters = letter_positions.keys.sort

  word = []
  # iterate through letters

  # for each letter, if there is more than one possible index, choose the smallest index that is larger 
  # than the chosen index for the last letter added or if all the indices are smaller than the last one added,
  # choose the smallest index

  # add the lowest value letter at its lowest possible index
  first_letter = letters[0]
  first_letter_position = letter_positions[first_letter][0]
  word[first_letter_position] = first_letter
  last_index_added = first_letter_position

  letters[1..(-1)].each do |letter|
    # if largest position of this letter is smaller than the index of the last letter added
    # use the smallest position for this letter
    if letter_positions[letter][-1] < last_index_added
      letter_position = letter_positions[letter][0]
      word[letter_position] = letter
      last_index_added = letter_position
      next
    end

    # add the smallest position that is greater than the position of the previous letter
    letter_positions[letter].each do |position|
      if position > last_index_added
        word[position] = letter
        last_index_added = position
        break
      end
    end
  end
  word.select { |letter| !!letter } # filter out nil items
end

p lexical_uniques("bcabc")
p lexical_uniques("cbacdcbc")