Reorganize String

Given string s, rearrange its characters so that no two adjacent characters are the same. Return the rearranged string, or "" if impossible.

Example 1

Input: "aab" → Output: "aba"

Example 2

Input: "aaab" → Output: ""

Solution Approach

Use a max-heap. Always pick the most frequent character that differs from the previous one. If most frequent equals previous, use second most frequent.

Count frequencies. Build max-heap of (freq, char) pairs.
While heap non-empty: pop max-freq char.
If it equals previous char: pop second, place it, push first back.
Else place first, push second back if freq > 0.
If heap has single element with freq > 1 and no prev different: return "".

Java

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c-'a']++;
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b)->b[0]-a[0]);
        for (int i = 0; i < 26; i++) if (freq[i] > 0) maxHeap.offer(new int[]{freq[i], i});
        StringBuilder sb = new StringBuilder();
        while (maxHeap.size() >= 2) {
            int[] first = maxHeap.poll(), second = maxHeap.poll();
            sb.append((char)('a'+first[1])); sb.append((char)('a'+second[1]));
            if (--first[0] > 0) maxHeap.offer(first);
            if (--second[0] > 0) maxHeap.offer(second);
        }
        if (!maxHeap.isEmpty()) {
            int[] last = maxHeap.poll();
            if (last[0] > 1) return "";
            sb.append((char)('a'+last[1]));
        }
        return sb.toString();
    }
}

Time Complexity: O(N log 26) = O(N)
Space Complexity: O(26) = O(1)