LeetCode : 767. Reorganize String

[congr]

https://leetcode.com/problems/reorganize-string/

[congr]

class Solution {
    class Pair {
        char ch;
        int cnt;
        Pair(char ch, int cnt) {
            this.ch = ch;
            this.cnt = cnt;
        }
    }

    public String reorganizeString(String S) {
        Map<Character, Integer> map = new HashMap();
        for (char c : S.toCharArray()) map.merge(c, 1, Integer::sum);

        PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> b.cnt - a.cnt);
        for (char c : map.keySet()) pq.add(new Pair(c, map.get(c)));

        Pair pre = null;
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Pair cur = pq.remove();
            sb.append(cur.ch);

            if (pre != null && pre.cnt > 0) pq.add(pre); // !!!

            cur.cnt--;
            pre = cur;       
            if (cur.cnt > 0 && pq.isEmpty()) return ""; // !!!
        }

        return sb.toString();
    }
}