Reorganize String

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.

If possible, output any possible result.  If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"
           

Example 2:

Input: S = "aaab"
Output: ""
           

Note:

• S

   will consist of lowercase letters and have length in range 

  [1, 500]

  .

思路1：用priorityqueue， O(nlog(26)) => O(N); 思想就是每次用最高的c交替進行填充，如何交替就是把c填了以後，不加入pq，然後用第二大的frequency的c去填，然後加入，再繼續，具體實作是用中間變量pre來儲存上一個頻率最大的，不加入queue，然後再加入queue的方法；

class Solution {
    private class Node {
        public char c;
        public int fre;
        public Node (char c, int fre) {
            this.c = c;
            this.fre = fre;
        }
    }
    
    public String reorganizeString(String S) {
        PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> (b.fre - a.fre));
        HashMap<Character, Integer> countmap = new HashMap<>();
        for(int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            countmap.put(c, countmap.getOrDefault(c, 0) + 1);
        }
        for(Character c: countmap.keySet()) {
            pq.offer(new Node(c, countmap.get(c)));
        }
        
        StringBuilder sb = new StringBuilder();
        Node pre = null;
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            sb.append(node.c);
            node.fre--;
            if(pre != null && pre.fre > 0) {
                pq.offer(pre);
            }
            pre = node;
        }
        return sb.length() == S.length() ? sb.toString() : "";
    }
}
           

思路2：這題可以用數學的思想做，也可以用priorityqueue做；

數學的思想就是，統計頻率以後，先用頻率最大的填0,2,4 然後繼續用c填 6,8,10 ...直到超出length範圍，然後從奇數位子開始填1,3,5 這樣就是一個不想臨的string；我個人比較喜歡前面一種用priorityqueue來解答的，可以拓展到 Rearrange String k Distance Apart 這題，這兩題其實非常類似；

class Solution {
    public String reorganizeString(String S) {
        if(S == null || S.length() == 0) {
            return S;
        }
        HashMap<Character, Integer> countMap = new HashMap<>();
        char maxc = S.charAt(0);
        int n = S.length();
        for(int i = 0; i < n; i++) {
            char c = S.charAt(i);
            countMap.put(c, countMap.getOrDefault(c, 0) + 1);
            if(countMap.get(c) > countMap.get(maxc)) {
                maxc = c;
            }
        }
        
        if(countMap.get(maxc) > (n + 1) / 2) {
            return "";
        }
        
        int index = 0;
        char[] res = new char[n];
        while(index < n && countMap.get(maxc) > 0) {
            res[index] = maxc;
            // 先安排0，2，4 偶數
            index += 2;
            countMap.put(maxc, countMap.get(maxc) - 1);
        }
        
        for(Character c: countMap.keySet()) {
            while(countMap.get(c) > 0) {
                //如果超出，返還奇數位子，1，3，5繼續
                if(index >= n) {
                    index = 1;
                }
                //然後接着inex繼續偶數安排 6,8, 10
                res[index] = c;
                index += 2;
                countMap.put(c, countMap.get(c) - 1);
            }
        }
        return String.valueOf(res);
    }
}