def best_shuffle(s)
  
  
  pos = []
  
  g = s.length.times.group_by { |i| s[i] }

  
  k = g.sort_by { |k, v| v.length }.map { |k, v| k }

  until g.empty?
    k.each do |letter|
      g[letter] or next
      pos.push(g[letter].pop)
      g[letter].empty? and g.delete letter
    end
  end

  
  
  
  letters = s.dup
  new =  * s.length
  until letters.empty?
    i, p = 0, pos.pop
    i += 1 while letters[i] == s[p] and i < (letters.length - 1)
    new[p] = letters.slice! i
  end

  score = new.chars.zip(s.chars).count { |c, d| c == d }
  [new, score]
end

%w(abracadabra seesaw elk grrrrrr up a).each do |word|
  puts  % [word, *best_shuffle(word)]
end