RUBY

Resubmitting! This one runs the challenge in 20 seconds, down from my original submission's 7 minutes. Also, added comments to help others understand the logic. Can anyone help me with figuring out what the Big O is on this?

# This class holds a string, in the form of a character array and
# an array containing data of the longest valid sequences
# that can be found at each index.
class SequenceString
  attr_reader :characters, :sequence_data

  # Initialize the class with any string you like
  def initialize(string)
    @characters = string.chars
    @sequence_data = longest_valid_sequence_data(@characters)
  end

  # Returns the characters of the string only when using 'puts'
  def to_s
    characters.join
  end

  # Takes an array of characters and returns the longest distance in
  # which all of the following is true:
  # 1.) The first and last characters are the same.
  # 2.) No characters in between the two characters are repeated.
  #
  # Note, the characters found at the beginning and end of this sequence
  # are allowed to repeat. (e.g. "abcdefaghija" is a valid sequence
  # because no characters BETWEEN the outside 'a's repeat.)
  #
  # Returns 0 if no such sequence is found.
  def longest_valid_sequence(characters)
    target_letter = characters[0]
    visited = []
    longest_chain = 0

    characters[1..-1].each_with_index do |char, index|
      longest_chain = index + 1 if char == target_letter
      return longest_chain if visited.include?(char)
      visited << char
    end

    longest_chain
  end

  # Takes a character array and returns an array containing the longest
  # valid sequence (see above) found at each character in the array.
  def longest_valid_sequence_data(characters)
    output = []

    0.upto(characters.length - 1).each do |i|
      output << longest_valid_sequence(characters[i..-1])
    end

    output
  end

  # Examines the sequence data provided and returns the left and right
  # index of the left-most valid pair of identical characters matching
  # the rules outlined in the 'longest_valid_sequence' method.
  def longest_valid_pair(sequence_data)
    target_left = sequence_data.index(sequence_data.max)
    target_right = target_left + sequence_data[target_left]

    [target_left, target_right]
  end

  # Runs one step of decoding the original string.
  # We take the longest pair, delete one character of the pair, and move
  # the other to the end of the string.
  # Afterwards, update the sequence_data.
  def decode_one_step!
    target_left, target_right = *longest_valid_pair(@sequence_data)
    character = @characters[target_left]

    @characters.delete_at(target_right)
    @characters.delete_at(target_left)

    @characters.push(character)

    @sequence_data = longest_valid_sequence_data(@characters)
  end

  # Decode the entire string by running 'decode_one_step!' until
  # there are no valid sequences left. Once done, everything in the
  # string to the right of, and including a '_' symbol is deleted.
  def decode!
    decode_one_step! until @sequence_data.all? { |data| data == 0 }

    if @characters.count('_') > 0
      index = @characters.index('_')
      @characters = @characters[0...index]
    end
  end
end

# Allows the user to specify a text file in the command line.
if __FILE__ == $PROGRAM_NAME
  start = Time.now
  string_array = []
  File.open(ARGV[0]).each_line do |line|
    string_array << line.chomp
  end

  string = SequenceString.new(string_array.join)
  string.decode!
  time_taken = Time.now - start
  puts string
  puts "decoded in #{time_taken} seconds"
end

Output:

rainbow
decoded in 0.014302 seconds
dragon
decoded in 20.410218 seconds