Reorganize String

Problem

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var reorganizeString = function(s) {
    // get frequency of characters in s
    const map = {};
    for (const c of s) {
        if (!(c in map)) {
            map[c] = 0;
        }
        map[c]++;
        if (map[c] > (s.length + 1) / 2) {
            return "";
        }
    }

    // push frequency character pairs into heap
    const maxHeap = new MaxPriorityQueue({ priority: o => o.frequency });
    for (const key in map) {
        maxHeap.enqueue({ char: key, frequency: map[key] });
    }

    // construct output string
    let res = [];
    while (!maxHeap.isEmpty()) {
        const remain = [];

        // get the top two frequency characters
        for (let i = 0; i <= 1 && !maxHeap.isEmpty(); i++) {
            const top = maxHeap.dequeue().element;
            res.push(top.char);
            top.frequency--;
            remain.push(top);
        }

        // push characters back into heap
        for (const o of remain) {
            if (o.frequency) {
                maxHeap.enqueue(o);
            }
        }

        // determine order of the two characters
        const n = res.length;
        if (res[n - 2] === res[n - 3]) {
            [res[n - 1], res[n - 2]] = [res[n - 2], res[n - 1]]
        }
    }
    return res.join("");
};

We will implement a greedy solution. First, we count the frequency of each character and store it in map. At the same time, based on the frequency, we check if a rearrangement of s is possible (ie. is there a character with frequency greater than (s.length + 1) / 2. Next, we push our frequency character pairs into a max-heap maxHeap. Using maxHeap, We construct our output string res two characters at a time. At each step, the two characters i, j will be the two with the highest frequency in maxHeap. Note that the order of i, j depends on the last character of res, hence the additional check at the end of the loop.

Problem​

Solution​

Problem

Solution