給定一個字符串S，檢查是否能重新排布其中的字母，使得兩相鄰的字符不同。

若可行，輸出任意可行的結果。若不可行，返回空字符串。

示例 1:

輸入: S = “aab”
輸出: “aba”

代碼

class Solution {public String reorganizeString(String S) {int[] temp=new int[26];int max=-1;for(int i=0;i<S.length();i++){max=Math.max(++temp[S.charAt(i)-'a'],max) ;}if(max>S.length()-max+1) return new String();//最大出現次數太大了，不可能交替出現StringBuilder stringBuilder=new StringBuilder();PriorityQueue<int[]> priorityQueue=new PriorityQueue<>((o1, o2) -> o2[1]-o1[1]);//最大堆for(int i=0;i<26;i++)//構造優先隊列if(temp[i]!=0)priorityQueue.add(new int[]{i,temp[i]});while (!priorityQueue.isEmpty())//每次選剩余容量最多的兩個字母{int[] t1=priorityQueue.poll(),t2=priorityQueue.poll();stringBuilder.append((char)(t1[0]+'a'));if(t2==null) return stringBuilder.toString();stringBuilder.append((char)(t2[0]+'a'));if(--t1[1]>0) priorityQueue.add(t1);if(--t2[1]>0) priorityQueue.add(t2);}return stringBuilder.toString();}
}