ReorganizeString767.java

/**
 * 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].
 */

public class ReorganizeString767 {
    public String reorganizeString(String S) {
        int[] hash = new int[26];
        for(char c : S.toCharArray()) hash[c-'a']++;
        int max = 0;
        for(int i = 0; i<26; ++i){
            if(hash[i] > hash[max]) max = i;
        }
        if(hash[max] > (S.length()+1)/2) return "";
        char[] res = new char[S.length()];
        int ptr = 0; 
        while(hash[max]-- > 0){
            res[ptr] = (char)(max + 'a');
            ptr += 2;
        }

        for(int i = 0; i<26; ++i){
            while(hash[i]-- > 0){
                if(ptr >= S.length()) ptr = 1;
                res[ptr] = (char)(i + 'a');
                ptr += 2;
            }
        }

        return new String(res);
    }


    /**
     * https://leetcode.com/problems/reorganize-string/solution/
     */
    public String reorganizeString2(String S) {
        int N = S.length();
        int[] count = new int[26];
        for (char c: S.toCharArray()) count[c-'a']++;
        PriorityQueue<MultiChar> pq = new PriorityQueue<MultiChar>((a, b) ->
            a.count == b.count ? a.letter - b.letter : b.count - a.count);

        for (int i = 0; i < 26; ++i) if (count[i] > 0) {
            if (count[i] > (N + 1) / 2) return "";
            pq.add(new MultiChar(count[i], (char) ('a' + i)));
        }

        StringBuilder ans = new StringBuilder();
        while (pq.size() >= 2) {
            MultiChar mc1 = pq.poll();
            MultiChar mc2 = pq.poll();
            /*This code turns out to be superfluous, but explains what is happening
            if (ans.length() == 0 || mc1.letter != ans.charAt(ans.length() - 1)) {
                ans.append(mc1.letter);
                ans.append(mc2.letter);
            } else {
                ans.append(mc2.letter);
                ans.append(mc1.letter);
            }*/
            ans.append(mc1.letter);
            ans.append(mc2.letter);
            if (--mc1.count > 0) pq.add(mc1);
            if (--mc2.count > 0) pq.add(mc2);
        }

        if (pq.size() > 0) ans.append(pq.poll().letter);
        return ans.toString();
    }

    class MultiChar {
        int count;
        char letter;
        MultiChar(int ct, char ch) {
            count = ct;
            letter = ch;
        }
    }

    // use 358. Rearrange String k Distance Apart
    public String reorganizeString3(String S) {
        return rearrangeString(S, 2);
    }

    public String rearrangeString(String str, int k) {
        int length = str.length();
        int[] count = new int[26];
        int[] nextIndex = new int[26];
        char[] chars = str.toCharArray();
        for (char ch: chars){
            count[ch-'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<length; i++) {
            int idx = findValidMax(count, nextIndex, i);
            if (idx == -1) return "";
            sb.append((char) (idx + 'a'));
            count[idx]--;
            nextIndex[idx] = i+k;
        }
        return sb.toString();
    }

    private int findValidMax(int[] count, int[] nextIndex, int index){
        int max = Integer.MIN_VALUE;
        int idx = -1;
        for (int i=0; i<26; i++) {
            if (count[i] != 0 && count[i] > max && index >= nextIndex[i]) {
                max = count[i];
                idx = i;
            }
        }
        return idx;
    }


    /**
     * https://leetcode.com/problems/reorganize-string/discuss/113451/7-ms-Java-O(n)-Solution.-no-Sorting
     */
    public String reorganizeString4(String S) {
        int n = S.length();
        int[] cnt = new int[128];
        char mc = 'a';
        for (char c : S.toCharArray()) {
            cnt[c]++;
            mc = (cnt[c] > cnt[mc]) ? c : mc;
        }
        if (cnt[mc] == 1) {
            return S;
        }
        if (n - cnt[mc] <= cnt[mc] - 2) {
            return "";
        }
        StringBuilder[] sb = new StringBuilder[cnt[mc]];
        for (int i = 0; i < sb.length; i ++) {
            sb[i] = new StringBuilder();
            sb[i].append(mc);
        }
        int k = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            while (c != mc && cnt[c] > 0) {
                sb[k++].append(c);
                cnt[c]--;
                k %= sb.length;
            }
        }
        for (int i = 1; i < sb.length; i++) {
            sb[0].append(sb[i]);
        }
        return sb[0].toString();
    }

}