import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

class Solution {
    public String reorganizeString(String S) {
        if (S.length() == 1)
            return S;
        //记录最大出现次数
        int maxCnt = 0;
        //记录各个字母出现次数
        HashMap<Character, Integer> map = new HashMap<>();
        //优先队列：按照字符出现次数从大到小排序
        PriorityQueue<Character> priorityQueue = new PriorityQueue<Character>(new Comparator<Character>() {
            @Override
            public int compare(Character pre, Character next) {
                return map.get(next) - map.get(pre);
            }
        });
        for (int i = 0; i < S.length(); i++) {
            Character ch = S.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
            maxCnt = Math.max(maxCnt, map.get(ch));
        }
        for (Character character : map.keySet()) {
            priorityQueue.add(character);
        }
        /*while(!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }*/
        //不符合直接返回""
        if (maxCnt > (S.length() + 1) / 2)
            return "";
        int flag = 0;
        StringBuilder sb = new StringBuilder();
        while (!priorityQueue.isEmpty()) {
            if (priorityQueue.size() == 1) {
                flag = 1;
                break;
            }
            Character pre = priorityQueue.poll();
//            System.out.println(pre);
            sb.append(pre);
            Character next = priorityQueue.poll();
            sb.append(next);
//            System.out.println(next);
            if (map.get(pre) > 1) {
                map.put(pre, map.get(pre) - 1);
                priorityQueue.add(pre);
            }
            if (map.get(next) > 1) {
                map.put(next, map.get(next) - 1);
                priorityQueue.add(next);
            }
        }
        if (flag == 1)
            sb.append(priorityQueue.poll());
        return sb.toString();
    }
}

链接：https://leetcode-cn.com/problems/reorganize-string/