767. Reorganize String

class Solution {
    public String reorganizeString(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Character> pq = new PriorityQueue((n1, n2) -> map.get(n2) - map.get(n1));
        pq.addAll(map.keySet());
        StringBuilder sb = new StringBuilder();
        while (pq.size() > 1) {
            char c1 = pq.poll();
            char c2 = pq.poll();
            sb.append(c1);
            sb.append(c2);
            map.put(c1, map.get(c1) - 1);
            map.put(c2, map.get(c2) - 1);
            if (map.get(c1) > 0) {
                pq.offer(c1);
            }
            if (map.get(c2) > 0) {
                pq.offer(c2);
            }
        }
        while (!pq.isEmpty()) {
            char c = pq.remove();
            if (map.get(c) > 1) {
                return "";
            }
            sb.append(c);
        }
        return sb.toString();
    }
}