Reorganize String

You are given a string, str. Rearrange its characters so that no two adjacent characters are the same.

Reorganize String

Problem Statement

You are given a string, str. Rearrange its characters so that no two adjacent characters are the same.

If it is possible to rearrange the string this way, return any one valid arrangement. If it is not possible, return an empty string.

Constraints

• 1 ≤ str.length ≤ 500
• The input string only has lowercase English letters.

Examples

Note: No examples were shared for this problem, so here are a few to illustrate it.

Example 1

Input: str = "aab"

Output: "aba"

Explanation: In "aba", no two characters next to each other are the same. This is one valid rearrangement.

Example 2

Input: str = "aaab"

Output: ""

Explanation: There are three "a"s and only one "b". There is no way to separate all three "a"s from each other, so no valid arrangement exists. We return an empty string.

Example 3

Input: str = "aabbcc"

Output: "abcabc"

Explanation: One possible rearrangement is "abcabc", where no character repeats next to itself. Other correct answers, like "abacbc", would also be accepted.

Solution

We use a max heap to solve this problem.

Steps

• First, we build a frequency map: how many times each character appears in str.
• We push every character, along with its count, into a max heap. This way, the character with the highest remaining count is always at the top.
• We build the result one character at a time:
  • We pop the character with the highest count from the heap. We add it to our result, and reduce its count by one.
  • We also keep track of the previous character we placed. If there was a previous character waiting, we push it back into the heap now, so it can be considered again in future rounds. This is what stops the same character from being placed twice in a row — we always "cool down" the last-placed character for one round.
  • If the character we just placed still has a count greater than 0, we save it as the new "previous" character, to be pushed back into the heap on the next round.
• If at any point we still have a "previous" character waiting, but the heap is empty, it means we can't avoid placing the same character twice in a row. In that case, no valid arrangement exists, so we return an empty string.
• If we make it through the whole string without this problem, we return the final result.

Code

function reorganizeString(str) {
    let charCounter = {};

    // Count frequency of each character
    for (let char of str) {
        charCounter[char] = (charCounter[char] || 0) + 1;
    }

    // Initialize heap with [count, char] pairs
    let maxHeap = new MaxHeap((a, b) => b[0] - a[0]);

    // Add all characters to heap
    for (let char in charCounter) {
        maxHeap.offer([charCounter[char], char]);
    }

    let previous = null;
    let result = "";

    while (maxHeap.size() || previous) {
        if (previous && maxHeap.size() === 0) {
            return "";
        }

        let [count, char] = maxHeap.poll();
        result += char;
        count--;

        // Push previous pair back
        if (previous) {
            maxHeap.offer(previous);
            previous = null;
        }

        // Store current pair as previous if count > 0
        if (count > 0) {
            previous = [count, char];
        }
    }

    return result;
}