字符串重新排列，让里面不能有相同字母在一起。比如aaabbb非法的，要让它变成ababab。给一种即可
Greedy:
跟FB面经Prepare task Schedule II很像，记录每个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
package ReorderString;
import java.util.*; public class Solution {
class Element {
char val;
int appear;
public Element(char value) {
this.val = value;
this.appear = 1;
}
} public String reorder(String str) {
Element[] summary = new Element[26];
for (int i=0; i<str.length(); i++) {
char cur = str.charAt(i);
if (summary[(int)(cur-'a')] == null) {
summary[(int)(cur-'a')] = new Element(cur);
}
else {
summary[(int)(cur-'a')].appear++;
}
}
PriorityQueue<Element> queue = new PriorityQueue<Element>(11, new Comparator<Element>() {
public int compare(Element e1, Element e2) {
return e2.appear - e1.appear;
}
}); for (Element each : summary) {
if (each != null) {
queue.offer(each);
}
}
Queue<Element> store = new LinkedList<Element>();
StringBuffer res = new StringBuffer();
while (!queue.isEmpty() || !store.isEmpty()) {
if (!queue.isEmpty()) {
Element cur = queue.poll();
if (res.length()==0 || cur.val!=res.charAt(res.length()-1)) {
res.append(cur.val);
cur.appear--;
if (cur.appear > 0) store.offer(cur);
while (!store.isEmpty()) {
queue.offer(store.poll());
}
}
else { //cur.val equals last char in res
store.offer(cur);
}
}
else { //store is not empty but queue is empty
res = new StringBuffer();
res.append(-1);
return res.toString();
}
}
return res.toString();
} /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
String res = sol.reorder("aaabbba");
System.out.println(res);
} }