767. Reorganize String

Given a stringS, 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:

• Swill consist of lowercase letters and have length in range[1, 500].

Thought:

1. Priority Queue + queue: Having two queues, ones pq: recording the priority of the element: the other with queue, record the use of previous charcter. First dump all the <int, char> pair into priority queue, then everytime pq pops() add it to the queue. if the top element of the queue has count < =0; then use one count, add it to the result string and take it back to priority queue until pq is empty and queue.size() <= 1. (Detailed implementation see the code)

2. Sort

3. Greedy + Sort (Optimized): sort the arr according to frequency, then insert the top half frequent into even position and bottom half, less frequent one into odd position. Final answer is return if the last two element is not the same (meaning

Code: Sort

class Solution {
public:
    string reorganizeString(string S) {
        // sort the string by occurance and reorder them as count * val;
        // having two pointers i,j: starting from 0, and (n-1)1/2 + 1, append the result sequentially from i and j
        int n = S.size();
        vector<int> m (26);
        for(char c : S)m[c-'a']++;
        vector<pair<int, char>> charCounts;
        for(int i = 0 ; i < 26; i++){
            if (m[i] > (n + 1)/2) return "";
            if(m[i]) charCounts.push_back({m[i], i+'a'});
        }

        sort(charCounts.rbegin(), charCounts.rend());
        string sorted;
        for(auto& p :charCounts)
            sorted += string(p.first, p.second);
        string ans;
        for(int i = 0, j = (n-1)/2 + 1; i <= (n-1)/2; i++, j++){
            ans += sorted[i];
            if(j < n) ans += sorted[j];
        }


        return ans;
    }
};

Greedy + Sort:

class Solution(object):
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        a = sorted(sorted(S), key=S.count)
        h = len(a) / 2
        a[1::2], a[::2] = a[:h], a[h:]
        return ''.join(a) * (a[-1:] != a[-2:-1])

PriorityQueue:

class Solution {
public:
    string reorganizeString(string S) {
        vector<int> m(26); int n =S.size();
        priority_queue<pair<int,char>>pq;
        queue<pair<int,char>>q;
        for(char c: S) m[c-'a']++;

        for(int i = 0; i < 26; i++){
            if (m[i] > (n+ 1) /2) return "";
            if(m[i]) pq.push({m[i], i + 'a'});
        }

        string ans;
        while(!pq.empty()||q.size() > 1){
            if(q.size() > 1){
                auto cur = q.front();
                q.pop();
                if(cur.first != 0) pq.push(cur);
            }
            if (!pq.empty()){
                auto cur = pq.top(); pq.pop();
                ans += cur.second;
                cur.first--;
                q.push(cur);
            }
        }

        return ans;
    }
};