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);
    }
}