Reorganize String

// C++
string reorganizeString(string s) {
    vector<int> freq(26, 0);
    for (char c : s) freq[c-'a']++;
    priority_queue<pair<int,char>> maxH;
    for (int i = 0; i < 26; i++) if (freq[i]) maxH.push({freq[i], 'a'+i});
    string res;
    while (maxH.size() >= 2) {
        auto [f1, c1] = maxH.top(); maxH.pop();
        auto [f2, c2] = maxH.top(); maxH.pop();
        res += c1; res += c2;
        if (f1 > 1) maxH.push({f1-1, c1});
        if (f2 > 1) maxH.push({f2-1, c2});
    }
    if (!maxH.empty()) {
        auto [f, c] = maxH.top();
        if (f > 1) return "";
        res += c;
    }
    return res;
}

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

// JavaScript — interleave approach
function reorganizeString(s) {
    const freq = new Array(26).fill(0);
    for (const c of s) freq[c.charCodeAt(0) - 97]++;
    const maxF = Math.max(...freq);
    if (maxF > Math.ceil(s.length / 2)) return '';
    const result = Array(s.length);
    let idx = 0;
    // Place most frequent first at even positions
    for (let i = 0; i < 26; i++) {
        while (freq[i] > 0) {
            if (idx >= s.length) idx = 1;
            result[idx] = String.fromCharCode(97 + i);
            idx += 2;
            freq[i]--;
        }
    }
    // Sort by frequency descending before placing
    const sorted = [...freq.entries()].sort((a, b) => b[1] - a[1]);
    const res2 = Array(s.length);
    let pos = 0;
    for (const [ci, f] of sorted) {
        for (let k = 0; k < f; k++) {
            if (pos >= s.length) pos = 1;
            res2[pos] = String.fromCharCode(97 + ci);
            pos += 2;
        }
    }
    return res2.join('');
}

# Python
import heapq
from collections import Counter

def reorganizeString(s):
    freq = Counter(s)
    max_heap = [(-f, c) for c, f in freq.items()]
    heapq.heapify(max_heap)
    result = []
    while len(max_heap) >= 2:
        f1, c1 = heapq.heappop(max_heap)
        f2, c2 = heapq.heappop(max_heap)
        result.extend([c1, c2])
        if f1 + 1 < 0: heapq.heappush(max_heap, (f1 + 1, c1))
        if f2 + 1 < 0: heapq.heappush(max_heap, (f2 + 1, c2))
    if max_heap:
        f, c = max_heap[0]
        if -f > 1:
            return ''
        result.append(c)
    return ''.join(result)