@@ -0,0 +1,2589 @@
+package greey;%0A%0Aimport java.util.Comparator;%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0Aimport java.util.PriorityQueue;%0A%0Apublic class ReorganizeString %7B%0A%0A    //TAG: Google%0A    //TAG: priority queue%0A    //TAG: Greedy%0A    //Difficulty: medium%0A%0A    /**%0A     * 767. Reorganize String%0A     * Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.%0A     *%0A     * If possible, output any possible result.  If not possible, return the empty string.%0A     *%0A     * Example 1:%0A     *%0A     * Input: S = %22aab%22%0A     * Output: %22aba%22%0A     * Example 2:%0A     *%0A     * Input: S = %22aaab%22%0A     * Output: %22%22%0A     * Note:%0A     *%0A     * S will consist of lowercase letters and have length in range %5B1, 500%5D.%0A     */%0A%0A    /*%0A    Solution:%0A    because current most char will be most possible to overflow, so greedy try to append current most count char%0A    use priorityQueue to save char,count pair and sort by descending count%0A%0A    Time: O(n) map + O(nlogn) pq + O(nlogn) poll = O(nlogn)%0A    Space: O(n) map + O(n)pq = O(n)%0A     */%0A%0A    public String reorganizeString(String S) %7B%0A        Map%3CCharacter, Integer%3E map = new HashMap%3C%3E();%0A        for (int i = 0; i %3C S.length(); i++) %7B%0A            char cur = S.charAt(i);%0A            map.put(cur, map.getOrDefault(cur, 0) + 1);%0A            if (map.get(cur) %3E (S.length() + 1)/2) return %22%22;%0A        %7D%0A        PriorityQueue%3CCharCount%3E queue = new PriorityQueue%3C%3E(new Comparator%3CCharCount%3E() %7B%0A            @Override%0A            public int compare(CharCount o1, CharCount o2) %7B%0A                return o2.count - o1.count;%0A            %7D%0A        %7D);%0A        for (Character key: map.keySet()) queue.offer(new CharCount(key, map.get(key)));%0A        StringBuilder builder = new StringBuilder();%0A        while (!queue.isEmpty()) %7B%0A            CharCount poll = queue.poll();%0A            if (builder.length() == 0 %7C%7C builder.charAt(builder.length() - 1) != poll.c) %7B%0A                builder.append(poll.c);%0A                poll.count--;%0A                if (poll.count %3E 0) queue.offer(poll);%0A            %7D else if (!queue.isEmpty()) %7B%0A                CharCount secPoll = queue.poll();%0A                builder.append(secPoll.c);%0A                secPoll.count--;%0A                if (secPoll.count %3E 0) queue.offer(secPoll);%0A                queue.offer(poll);%0A            %7D%0A        %7D%0A        return builder.toString();%0A    %7D%0A%0A    class CharCount %7B%0A        char c;%0A        int count;%0A        public CharCount(char c, int count) %7B%0A            this.c = c;%0A            this.count = count;%0A        %7D%0A    %7D%0A%0A%7D%0A

767. Reorganize String