767. Reorganize String

/*
Time Complexity: O(N log N)
Space Complexity: O(N)

N = Length of the input string.
*/
class Solution {
    public String reorganizeString(String S) {
        if (S == null || S.length() == 0) {
            return "";
        }
        if (S.length() == 1) {
            return S;
        }

        Map<Character, Integer> countMap = new HashMap();
        for (char c : S.toCharArray()) {
            countMap.put(c, countMap.getOrDefault(c, 0)+1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<Map.Entry<Character, Integer>>(
            (a,b) -> (a.getValue() != b.getValue() ? b.getValue() - a.getValue() : a.getKey() - b.getKey()));
        queue.addAll(countMap.entrySet());

        StringBuilder sb = new StringBuilder();

        while (queue.size() >= 2) {
            Map.Entry<Character, Integer> firstEntry = queue.poll();
            Map.Entry<Character, Integer> secondEntry = queue.poll();
            sb.append(firstEntry.getKey());
            sb.append(secondEntry.getKey());
            if (firstEntry.getValue() > 1) {
                firstEntry.setValue(firstEntry.getValue() - 1);
                queue.offer(firstEntry);
            }
            if (secondEntry.getValue() > 1) {
                secondEntry.setValue(secondEntry.getValue() - 1);
                queue.offer(secondEntry);
            }
        }

        if (queue.size() == 1) {
            sb.append(queue.poll().getKey());
        }

        return sb.length() == S.length() ? sb.toString() : "";
    }
}