字符串重新排列，让里面不能有相同字母在一起。比如aaabbb非法的，要让它变成ababab。给一种即可

Greedy:

跟很像，记录每个char出现次数，然后用最大堆，把剩下char里面出现次数多的优先Poll出来组建新的string

如果poll出来的char跟上一个相同，则用一个queue暂时存一下

我觉得时间复杂度：O(N) + O(KlogK) + O(NlogK) = O(NlogK) ,where K is the number of different character in the string

1 package ReorderString; 2 import java.util.*; 3  4 public class Solution { 5     class Element { 6         char val; 7         int appear; 8         public Element(char value) { 9             this.val = value;10             this.appear = 1;11         }12     }13     14     public String reorder(String str) {15         Element[] summary = new Element[26];16         for (int i=0; i
     
       queue = new PriorityQueue
      
       (11, new Comparator
       
        () {26             public int compare(Element e1, Element e2) {27                 return e2.appear - e1.appear;28             }29         });30         31         for (Element each : summary) {32             if (each != null) {33                 queue.offer(each);34             }35         }36         Queue
        
          store = new LinkedList
         
          ();37         StringBuffer res = new StringBuffer();38         while (!queue.isEmpty() || !store.isEmpty()) {39             if (!queue.isEmpty()) {40                 Element cur = queue.poll();41                 if (res.length()==0 || cur.val!=res.charAt(res.length()-1)) {42                     res.append(cur.val);43                     cur.appear--;44                     if (cur.appear > 0) store.offer(cur);45                     while (!store.isEmpty()) {46                         queue.offer(store.poll());47                     }48                 }49                 else { //cur.val equals last char in res50                     store.offer(cur);51                 }52             }53             else { //store is not empty but queue is empty54                 res = new StringBuffer();55                 res.append(-1);56                 return res.toString();57             }58         }59         return res.toString();60     }61     62 63     /**64      * @param args65      */66     public static void main(String[] args) {67         // TODO Auto-generated method stub68         Solution sol = new Solution();69         String res = sol.reorder("aaabbba");70         System.out.println(res);71     }72 73 }