Reorganize String solution and explanation

import heapq
from collections import Counter

def reorganize_string(s: str) -> str:
    freq = Counter(s)
    max_heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(max_heap)

    prev_count, prev_char = 0, ''
    result = []

    while max_heap:
        count, char = heapq.heappop(max_heap)
        result.append(char)

        if prev_count < 0:
            heapq.heappush(max_heap, (prev_count, prev_char))

        prev_count, prev_char = count + 1, char

    if len(result) != len(s):
        return ""
    return "".join(result)

import java.util.PriorityQueue;
import java.util.HashMap;

public class ReorganizeString {
    public String reorganizeString(String s) {
        HashMap<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> frequencyMap.get(b) - frequencyMap.get(a));
        maxHeap.addAll(frequencyMap.keySet());

        StringBuilder result = new StringBuilder();
        while (maxHeap.size() > 1) {
            char first = maxHeap.remove();
            char second = maxHeap.remove();
            result.append(first);
            result.append(second);
            frequencyMap.put(first, frequencyMap.get(first) - 1);
            frequencyMap.put(second, frequencyMap.get(second) - 1);

            if (frequencyMap.get(first) > 0) maxHeap.add(first);
            if (frequencyMap.get(second) > 0) maxHeap.add(second);
        }

        if (!maxHeap.isEmpty()) {
            char last = maxHeap.remove();
            if (frequencyMap.get(last) > 1) return "";
            result.append(last);
        }

        return result.toString();
    }
}

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string reorganizeString(string s) {
    vector<int> count(26, 0);
    int n = s.size();
    for (char c : s) count[c - 'a']++;

    int maxCount = *max_element(count.begin(), count.end());
    if (maxCount > (n + 1) / 2) return "";

    string result(n, ' ');
    int evenIndex = 0, oddIndex = 1;
    for (int i = 0; i < 26; i++) {
        while (count[i] > 0 && count[i] <= n / 2 && oddIndex < n) {
            result[oddIndex] = 'a' + i;
            oddIndex += 2;
            count[i]--;
        }
        while (count[i] > 0) {
            result[evenIndex] = 'a' + i;
            evenIndex += 2;
            count[i]--;
        }
    }

    return result;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* reorganizeString(char* s) {
    int n = strlen(s);
    int count[26] = {0};

    for (int i = 0; i < n; i++)
        count[s[i] - 'a']++;

    int maxCount = 0, letter = 0;
    for (int i = 0; i < 26; i++) {
        if (count[i] > maxCount) {
            maxCount = count[i];
            letter = i;
        }
    }

    if (maxCount > (n + 1) / 2) return "";

    char* result = (char*)malloc((n + 1) * sizeof(char));
    result[n] = '\0';

    int index = 0;
    while (count[letter]--) {
        result[index] = letter + 'a';
        index += 2;
    }

    for (int i = 0; i < 26; i++) {
        while (count[i]--) {
            if (index >= n) index = 1;
            result[index] = i + 'a';
            index += 2;
        }
    }

    return result;
}

func reorganizeString(s string) string {
	cnt := make([]int, 26)
	for _, c := range s {
		t := c - 'a'
		cnt[t]++
	}
	mx := slices.Max(cnt)
	n := len(s)
	if mx > (n+1)/2 {
		return ""
	}
	m := [][]int{}
	for i, v := range cnt {
		if v > 0 {
			m = append(m, []int{v, i})
		}
	}
	sort.Slice(m, func(i, j int) bool {
		return m[i][0] > m[j][0]
	})
	ans := make([]byte, n)
	k := 0
	for _, e := range m {
		v, i := e[0], e[1]
		for v > 0 {
			ans[k] = byte('a' + i)
			k += 2
			if k >= n {
				k = 1
			}
			v--
		}
	}
	return string(ans)
}

use std::collections::{BinaryHeap, HashMap, VecDeque};

impl Solution {
    #[allow(dead_code)]
    pub fn reorganize_string(s: String) -> String {
        let mut map = HashMap::new();
        let mut pq = BinaryHeap::new();
        let mut ret = String::new();
        let mut queue = VecDeque::new();
        let n = s.len();

        // Initialize the HashMap
        for c in s.chars() {
            map.entry(c)
                .and_modify(|e| {
                    *e += 1;
                })
                .or_insert(1);
        }

        // Initialize the binary heap
        for (k, v) in map.iter() {
            if 2 * *v - 1 > n {
                return "".to_string();
            } else {
                pq.push((*v, *k));
            }
        }

        while !pq.is_empty() {
            let (v, k) = pq.pop().unwrap();
            ret.push(k);
            queue.push_back((v - 1, k));
            if queue.len() == 2 {
                let (v, k) = queue.pop_front().unwrap();
                if v != 0 {
                    pq.push((v, k));
                }
            }
        }

        if ret.len() == n {
            ret
        } else {
            "".to_string()
        }
    }
}