Leetcode 767. 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].

Solution:
use a priority queue.

Code (Java):

class Solution {
    public String reorganizeString(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        // step 1: check word count for each char
        //
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            counts[c - 'a']++;

            if (counts[c - 'a'] > (int)Math.ceil((double)s.length() / 2)) {
                return "";
            }
        }

        // step 2: put the count into a pq
        //
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>(new MyPairComparator());
        for (int i = 0; i < counts.length; i++) {
            Pair pair = new Pair(counts[i], (char)(i + 'a'));
            pq.offer(pair);
        }

        // construct the result
        //
        StringBuilder sb = new StringBuilder();
        while (sb.length() < s.length()) {
            Pair pair = pq.poll();
            if (sb.length() == 0 || sb.charAt(sb.length() - 1) != pair.c) {
                sb.append(pair.c);
                pair.count--;
                //if (pair.count > 0) {
                    pq.offer(pair);
                //}
            } else {
                // pull the head and get the second biggest
                //
                Pair sec = pq.poll();
                sb.append(sec.c);
                sec.count--;
                //if (sec.count > 0) {
                    pq.offer(sec);
                //}
                pq.offer(pair);
            }
        }

        return sb.toString();
    }
}


class Pair {
    int count;
    char c;

    public Pair (int myCount, char myChar) {
        count = myCount;
        c = myChar;
    }
}

class MyPairComparator implements Comparator<Pair> {
    public int compare(Pair a, Pair b) {
        return b.count - a.count;
        
    }
}

Update on 5/23/19

/*
 * @lc app=leetcode id=767 lang=java
 *
 * [767] Reorganize String
 */
class Solution {
    public String reorganizeString(String S) {
        if (S == null || S.length() == 0) {
            return "";
        }

        // step 1: do the word count
        int[] counts = new int[26];
        for (int i = 0 ; i < S.length(); i++) {
            char c = S.charAt(i);
            counts[c - 'a'] += 1;
        }

        // step2: sort the word count 
        PriorityQueue<Pair> pq = new PriorityQueue<>(new MyPairComparator());
        
        for (int i = 0; i < 26; i++) {
            if (counts[i] == 0) {
                continue;
            }
            Pair pair = new Pair((char)(i + 'a'), counts[i]);
            pq.offer(pair);
        }

        if (pq.peek().count > (S.length() + 1) / 2) {
            return "";
        }

        StringBuilder ans = new StringBuilder();
        while (!pq.isEmpty()) {
            Pair top = pq.poll();
            if (ans.length() > 0 && top.c == ans.charAt(ans.length() - 1)) {
                Pair secondTop = pq.poll();
                pq.offer(top);
                top = secondTop;
            }

            ans.append(top.c);
            top.count -= 1;

            if (top.count > 0) {
                pq.offer(top);
            }
        }

        return ans.toString();
    }
}

class Pair {
    char c;
    int count;
    public Pair(char c, int count) {
        this.c = c;
        this.count = count;
    }
}

class MyPairComparator implements Comparator<Pair> {
    @Override
    public int compare(Pair a, Pair b) {
        return b.count - a.count;
    }
}