title: Shuffling a string so that no two adjacent letters are the same
body: <p>I've been trying to solve this interview problem which asks to shuffle a string so that no two adjacent letters are identical 
  For example, </p>
  
  <p>ABCC -> ACBC </p>
  
  <p>The approach I'm thinking of is to</p>
  
  <blockquote>
    <p>1) Iterate over the input string and store the (letter, frequency)
    pairs in <em>some</em> collection</p>
    
    <p>2) Now build a result string by pulling the highest frequency (that is > 0) letter that we didn't just pull</p>
    
    <p>3) Update (decrement) the frequency whenever we pull a letter</p>
    
    <p>4) return the result string if all letters have zero frequency</p>
    
    <p>5) return error if we're left with only one letter with frequency greater than 1</p>
  </blockquote>
  
  <p>With this approach we can save the more precious (less frequent) letters for last. But for this to work, we need a collection that lets us efficiently query a key and at the same time efficiently sort it by values. Something like <a href="https://stackoverflow.com/questions/289/how-do-you-sort-a-dictionary-by-value">this</a> would work except we need to keep the collection sorted after every letter retrieval.</p>
  
  <p>I'm assuming Unicode characters.</p>
  
  <p>Any ideas on what collection to use? Or an alternative approach?</p>